传送门：https://www.51nod.com/Challenge/Problem.html##problemId=1588
题意
定义幸运数字只由4和7组成，比如4，7，47。
给一棵树，要我们找到三元组(i,j,k)，两两之间的路径中必须要有一条由幸运数字组成的边。
问，存在多少组这样的三元组。
思路
幸运数字好处理，check一下。关键是怎么找出贡献。
统计树上方案数，一般先固定一个点，比如i，然后再找另外两个点j和k，算出i这个点对应的贡献。
设f[u]为以u为根节点的子树中，有几个点到u的路径中存在幸运数字。 设h[u]为以u为根节点的子树外，有几个点到u的路径中存在幸运数字。
这样，我们的j和k的选择就可以在f中选择，或者h中选择，或者f和h中选择。
即i的贡献为$f[i]*(f[i]-1)+h[i]*(h[i]-1)+f[i]*h[i]*2$
然后就是处理f和h。
dfs过程中：
- 如果u和v的边是幸运数字，则$f[u]+=siz[v]$
- 否则$f[u]+=f[v]$
- 如果v和u的边是幸运数字，则$h[v]+=siz[1]-siz[v]$
- 否则$h[v]+=h[u]+f[u]-f[v]$
所以要先dfs一遍预处理f和siz，然后dfs一遍处理h，最后统计方案。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
struct Edge {
int v, w;
};
vector<Edge> g[N];
ll f[N], h[N];
int siz[N];
void dfs1(int u, int fa) {
siz[u] = 1;
for(auto e : g[u]) {
int v = e.v;
if(v == fa) continue;
dfs1(v, u);
siz[u] += siz[v];
if(e.w) f[u] += siz[v];
else f[u] += f[v];
}
}
void dfs2(int u, int fa) {
for(auto e : g[u]) {
int v = e.v;
if(v == fa) continue;
if(e.w) h[v] = siz[1] - siz[v];
else h[v] = h[u] + f[u] - f[v];
dfs2(v, u);
}
}
int check(int n) {
while(n) {
if(n % 10 != 4 && n % 10 != 7) return 0;
n /= 10;
}
return 1;
}
void solve() {
int n; cin >> n;
for(int i = 1;i < n; i++) {
int u, v, w; cin >> u >> v >> w;
w = check(w);
g[u].push_back(Edge{v, w});
g[v].push_back(Edge{u, w});
}
dfs1(1, -1);
dfs2(1, -1);
ll ans = 0;
for(int i = 1;i <= n; i++) ans += f[i] * (f[i] - 1) + h[i] * (h[i] - 1) + f[i] * h[i] * 2;
cout << ans << endl;
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/27/51nod1588/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！