dsu on tree 概括

适合用来解决有如下特性的（树上）问题：

1、只有查询而没有修改

2、对子树的查询结果可以直接（或者较低时间复杂度修改后）用于其父结点。

暴力算法

扫描每棵子树，扫描完之后再返回上一层，扫描父结点对应的子树。

极端情况时间复杂度 O （ N 2 ） O（N^2） O（N2）

考虑优化

首先我们知道对子树的查询结果可以用于父结点，考虑空间复杂度，我们仅保留某一次的查询结果。借用树剖的思想，我们选择保留最大的一棵子树的查询结果，这样可以尽可能地减少遍历次数。把时间复杂度降到 O （ N l o g N ） O（NlogN） O（NlogN）

代码

Codforces 600E

#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int n,ma;
int h[maxn],p[maxn*2],nxt[maxn*2],c[maxn];
long long ans[maxn],siz[maxn],son[maxn],cnt[maxn],su[maxn];//cnt:对颜色的计数 su:数量为i的所有颜色之和 
void add(int now,int f,int val)
{
	for(int i=h[now];i;i=nxt[i])
	{
		if(p[i]!=f&&!son[p[i]]) add(p[i],now,val);//不计算被标记为重儿子的子树（因为已经计算过了） 
	}
	su[cnt[c[now]]]-=c[now];
	cnt[c[now]]+=val;
	su[cnt[c[now]]]+=c[now];
	if(val+1)
	{
		if(su[ma+1]) ma++;
	}else
	{
		if(!su[ma])ma--;
	}
	return;
}
int sea(int now,int f)//预处理，计算每个子树的大小 
{
	int mx,son_;
	siz[now]=1;
	for(int i=h[now];i;i=nxt[i])
	if(p[i]!=f)
	{
		sea(p[i],now);
		siz[now]+=siz[p[i]];
	}
	return 0;	
}
int dfs(int now,int f,int keep)//keep标记用来说明是否要保留影响 
{
	int son_,mx;
	mx=son_=-1;
	for(int i=h[now];i;i=nxt[i])
	if(p[i]!=f)if(siz[p[i]]>mx)mx=siz[p[i]],son_=p[i];//记录重儿子 
	for(int i=h[now];i;i=nxt[i])
	if(p[i]!=f&&p[i]!=son_)
	{
		dfs(p[i],now,0);//计算所有非重儿子的子树，清除影响 
	}
	if(son_!=-1)
	{son[son_]=1;dfs(son_,now,1);}//标记重儿子，计算重儿子子树，不清除影响 
	add(now,f,1);//这里加入所有非重儿子的子树，在这个函数里检查标记看是否为重儿子，是则不计算对应子树 
	if(son_!=-1)son[son_]=0;//清除标记，为后面的清理做准备（如果keep为1也要清） 
	ans[now]=su[ma];
	if(!keep)//不保留影响则清除，此时重儿子标记已经删除，所以会清理整棵子树的影响 
	add(now,f,-1),ma=0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&c[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		p[i*2-1]=y;nxt[i*2-1]=h[x];h[x]=i*2-1;
		p[i*2]=x;nxt[i*2]=h[y];h[y]=i*2;
	}
	sea(1,0);
	dfs(1,0,1);
	for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
	return 0;
}