牛客多校九 - Here is an Easy Problem of Zero-chan (树形DP，推公式，贡献)

https://ac.nowcoder.com/acm/contest/38727/H

题意
给定一棵根节点为 1 的树，定义 $f(x)={\prod }_{i=1}^{n}lca(x,i)$。
求每个节点 x 的 $f(x)$ 的后缀 0 个数。

$1\le n\le 10^5$

思路
一开始看到后缀 0 的时候是懵的，这怎么搞，还是在树上。后来分析才发现，只有 2 和 5 相乘才会构成 0，所以只需要用 2 和 5 来转移，看与其他节点的 lca 中，一共有多少个 2 和 5，两者最小值便是后缀 0 的个数。

在一棵树中，一个点与所有点求 lca，有两种思路：

思路1：考虑每个点作为 lca，将其他点的贡献更新。
如果当前节点作为其余两点的 lca 的话，那么这两点一定在以当前节点为根的子树中，所以对于每个点只能对其子树中的点有贡献。

如图，根节点对左边子树中所有点的贡献都是 右边点的个数 * 根节点中 2 或 5 的个数。

但在dfs的过程中，每次只能对当前节点直接相连的子节点更新，而不能对子节点下面的节点更新。但是在递归到子节点下面节点时，可以继承其父节点的答案，也就相当于把下面节点也更新了。

当回溯之后，再加上子树中所有节点对当前节点的贡献，即节点数 * 当前节点的 2 或 5 的个数。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int cnt2[N], cnt5[N], sum[N];
vector<int> e[N];
int ans2[N], ans5[N];

void init(int x, int fa)
{
	sum[x] = 1;
	for(int tx : e[x])
	{
		if(tx == fa) continue;
		init(tx, x);
		sum[x] += sum[tx];
	}
}

void dfs(int x, int fa)
{
	for(int tx : e[x])
	{
		if(tx == fa) continue;
		ans2[tx] += ans2[x], ans5[tx] += ans5[x];
		ans2[tx] += cnt2[x] * (sum[x] - sum[tx]);
		ans5[tx] += cnt5[x] * (sum[x] - sum[tx]);
		dfs(tx, x);
	}
	ans2[x] += cnt2[x] * sum[x];
	ans5[x] += cnt5[x] * sum[x];
}

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++) 
	{
		int x = i;
		while(x % 5 == 0) cnt5[i]++, x/=5;
		while(x % 2 == 0) cnt2[i]++, x/=2;
	}
	
	for(int i=1;i<n;i++)
	{
		int x, y; cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	init(1, 0);
	
	dfs(1, 0);
	
	while(m--)
	{
		int x; cin >> x;
		cout << min(ans2[x], ans5[x]) << endl;
	}
	
	return 0;
}
/*
10 10
1 5
1 10
2 5
5 4
2 3
4 6
4 7
10 9
10 8
1 2 3 4 5 6 7 8 9 10
*/
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

思路2：直接考虑每个点与所有点求 lca 的答案
对于树中的一个节点来说，其与所有点的 lca 无非只有两种情况：要么那个点在当前节点的子树中，lca 为当前节点；要么 lca 在从根节点到当前节点的路径上。

对于图中点 c 来说，所有点都被分成了三块区域，第一块区域的 lca 为 a，第二块区域的 lca 为 b，第三块区域的 lca 为 c，那么 c 点最后的答案为：第一块区域点的数量 * a的属性 + 第二块区域点数 * b的属性 + 第三块区域点数 * c的属性。
如何求的每一块区域的大小，将 a 节点子节点个数 - b 节点子节点个数便是第一块区域点的个数。
但是现在的如果直接求的话，要遍历到根节点的所有节点，复杂度是 n^2 的，要想办法优化。

分别写出节点 a，b，c 的答案：

分析式子发现：
当前节点 x 的答案可以直接用父节点 fa 的答案直接转移过来：ans[x] = ans[fa] + sum[x]*(cnt[x] - cnt[fa])，那么此时就可以直接 dfs 用父节点更新当前节点即可。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int cnt2[N], cnt5[N];
int ans2[N], ans5[N];
int sum[N];
vector<int> e[N];

void init(int x, int fa)
{
	sum[x] = 1;
	for(int tx : e[x])
	{
		if(tx == fa) continue;
		init(tx, x);
		sum[x] += sum[tx];
	}
}

void dfs(int x, int fa)
{
	for(int tx : e[x])
	{
		if(tx == fa) continue;
		ans2[tx] = ans2[x] + sum[tx] * (cnt2[tx] - cnt2[x]);
		ans5[tx] = ans5[x] + sum[tx] * (cnt5[tx] - cnt5[x]);
		dfs(tx, x);
	}
}

signed main(){
	Ios;
	cin >> n >> m;
	for(int i=1;i<n;i++)
	{
		int x, y; cin >> x >> y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	
	for(int i=1;i<=n;i++){
		int x = i;
		while(x % 2 == 0) x /= 2, cnt2[i] ++;
		while(x % 5 == 0) x /= 5, cnt5[i] ++;
	}
	
	init(1, 0);
	
	dfs(1, 0);
	
	while(m--)
	{
		int x; cin >> x;
		cout << min(ans2[x], ans5[x]) << endl;
	}
	
	return 0;
}
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
63

---

经验

从特殊到普遍，一点一点推式子，很重要！

有时候样例给的图形不好看出来规律，不要一直死扣这个图，另外在画一个寻找普遍规律。