自动搬运

查看原文

来自洛谷，原作者为

	xxseven 所有梦想，终有绽放之时

搬运于2025-08-24 21:40:48，当前版本为作者最后更新于2024-09-03 15:21:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

子树数颜色问题居然没有树上启发式合并的题解？

首先观察题面，$2$ 到 $n$ 的每一个点都有唯一的入边，保证点 $1$ 能到达任意点，这不就是一棵只能往下走的树嘛。

那么，一个点能走到的位置也就是它子树内的所有节点了。也就是说，对于每一次询问的节点，我们要求出它子树内的不同礼物种类。

对于这个问题我们有一个很优秀的解法：树上启发式合并。

顾名思义，这种方法运用了启发式的思想。首先我们有朴素算法：对于每个节点，暴力统计出子树内的所有信息。

这个时候，有人开始发扬人类智慧，想到：之前的做法每次都要清空统计的数组，但是我们可以保留其中一个子树的信息，这样就可以少统计一部分了。那么保留哪个子树呢？显然是要保留大小最大的了，也就是重链剖分里的重儿子。

可以证明，按照这样的方式，每个节点被重复统计的次数等于它到根的轻边个数，而这个数是 $O(\log n)$ 级别的，因此总时间复杂度即为 $O(n \log n)$。

代码非常好写，因为这其实就是一个暴力。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+6;
int n,m,ans[N],buck[N],cnt,a[N];
vector<int> f[N];
int fa[N],dep[N],son[N],siz[N];
void dfs(int x,int y){
	dep[x]=dep[y]+1; siz[x]=1;
	for(int u:f[x]){
		if(u==y) continue;
		dfs(u,x); siz[x]+=siz[u];
		if(siz[u]>siz[son[x]]) son[x]=u;
	}
}
void calc(int x,int son,int sgn){ //暴力递归统计子树
	if(!buck[a[x]]) cnt++;
	buck[a[x]]+=sgn;
	if(!buck[a[x]]) cnt--;
	for(int u:f[x]){
		if(u==son||u==fa[x]) continue;
		calc(u,son,sgn);
	}
}
void dfs2(int x,int flag){//flag表示该节点是否是重儿子，即是否要清空
	for(int u:f[x]){
		if(u!=fa[x]&&u!=son[x]) dfs2(u,0);
	}
	if(son[x]) dfs2(son[x],1);
	calc(x,son[x],1);
	ans[x]=cnt;//对于每个节点存下答案
	if(flag) return;//如果是重儿子，则跳过清空步骤
	calc(x,-1,-1);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;++i){
		cin>>fa[i];
		f[i].push_back(fa[i]);
		f[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;++i) cin>>a[i];
	dfs(1,0); dfs2(1,1);
	cin>>m;
	for(int x,i=1;i<=m;++i){
		cin>>x; cout<<ans[x]<<'\n';
	}
	return 0;
}

希望这篇题解能够帮到你！