22河南省赛 - J. Mex Tree（LCA，MEX）

https://codeforces.com/gym/103941

题意
给定 n 个节点的树，每个节点编号为 1, 2, 3, …, n，第 i 个点的权值为 $v_i$，$v_1,v_2,...,v_n$ 是 $0,1,...,n-1$ 的一个排列。

对于 k = 0, 1, 2,…, n，找到最大的连通块使得其中所有点权值的 MEX 恰好为 k，输出最大满足的连通块大小。

$1\le n\le 10^6$

思路
连通块中所有点的权值的 MEX 恰好为 k，也就是说连通块中至少要出现权值为 1~k-1 的 k-1 个点，并且权值为 k 的节点不在连通块中。

然后注意到这是一棵树，如果说权值为 k 的节点 x 不在连通块中，那么节点 x 所在的子树将会和整个连通块分开，所以：

• 如果权值为 1~k-1 的 k-1 个节点都不在节点 x 的子树中，那么满足的最大连通块就是除了节点 x 所在子树外其余所有点；
  判断：如果节点 x 所在子树中所有节点的最小权值为 k 的话，那么就说明权值 1~k-1 的 k-1 个节点都不在节点 x 的子树中，答案为 n - cnt[x]。
• 如果权值为 1~k-1 的 k-1 个节点的 lca 的深度 <= x 的深度，说明这 k-1 个节点如果放在一个连通块中，必定要经过节点 x，无解；
• 然后剩下的最后一种情况就是，1~k-1 这 k-1 个节点在节点 x 的某个子树中，这样最大的子树就是满足的最大连通块。
  判断：节点 x 的儿子为根的子树便是最大的子树，遍历其所有儿子节点，所在子树中所有节点的最小点权为 0 的那个儿子节点便是 k-1 个节点所在的子树，答案为该子树大小。

需要注意的是，k = 0 时不需要满足所有小于 k 的节点都在连通块中，所以取该节点上部和下部连通块的最大值作为答案。

#include
using namespace std;

const int N = 1000010;
int n, m, a[N];
int dep[N], f[N][30], k;
int mina[N], mp[N], cnt[N];
vector<int> e[N];

void dfs(int x, int fa)
{
	mina[x] = a[x];
	cnt[x] = 1;
	for(int tx : e[x])
	{
		if(tx == fa) continue;
		
		dep[tx] = dep[x] + 1;
		f[tx][0] = x;
		for(int i=1;i<=k;i++)
			f[tx][i] = f[f[tx][i-1]][i-1];
		
		dfs(tx, x);
		mina[x] = min(mina[x], mina[tx]);
		cnt[x] += cnt[tx];
	}
}

int lca(int x, int y)
{
	if(dep[x] < dep[y]) swap(x, y);
	
	for(int i=k;i>=0;i--)
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	
	if(x == y) return x;
	
	for(int i=k;i>=0;i--)
		if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	
	return f[x][0];
}

int main(){
	scanf("%d", &n);
	k = log(n)/log(2);
	
	for(int i=1;i<=n;i++) scanf("%d", &a[i]), mp[a[i]] = i;
	
	for(int i=2;i<=n;i++)
	{
		int x; scanf("%d", &x);
		e[x].push_back(i);
		e[i].push_back(x);
	}
	
	dep[1] = 1;
	dfs(1, 0);
	
	int Lca = 0;
	for(int i=0;i<=n;i++)
	{
		int x = mp[i];
		
		if(i == 0)
		{
			int maxa = n - cnt[x];
			for(int tx : e[x])
			{
				if(tx == f[x][0]) continue;
				maxa = max(maxa, cnt[tx]);
			}
			cout << maxa << ' ';
		}
		else if(mina[x] >= a[x]){
			cout << n - cnt[x] << ' ';
		}
		else if(dep[Lca] <= dep[x]) cout << 0 << ' ';
		else
		{
			for(int tx : e[x])
			{
				if(tx == f[x][0]) continue;
				if(mina[tx] == 0){
					cout << cnt[tx] << ' ';
					break;
				}
			}
		}
		if(!Lca) Lca = x;
		else Lca = lca(Lca, x);
	}
	
	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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

场上做出来了，很激动~