dsu on tree模板题

dsu on tree详解

暴力显然\(O(n^2)\) O(TLE)

我们发现，在 对某个节点的树做统计 前，最后一个儿子的那棵子树统计不用清空

并且，这个不用清空的儿子size越大，显然越优挑size最大的来就行

O(nlogn)

#include<iostream>
#include<cstdio>
#define LL long long
using namespace std;
int n,x,y,tot,mx,Son;
LL nowans;
const int N=100010;
int col[N],head[N],to[N<<1],nt[N<<1],siz[N],son[N],cnt[N];
LL ans[N];
void add(int f,int t)
{
	to[++tot]=t;nt[tot]=head[f];head[f]=tot;
}
void dfs1(int x,int fa)
{
	siz[x]=1;
	for(int i=head[x];i;i=nt[i])
		if(to[i]!=fa)
		{
			dfs1(to[i],x);
			siz[x]+=siz[to[i]];
			if(siz[to[i]]>siz[son[x]])son[x]=to[i];
		}
}
void ADD(int x,int fa,int val)
{
	cnt[col[x]]+=val;
	if(cnt[col[x]]>mx)mx=cnt[col[x]],nowans=col[x];
	else if(cnt[col[x]]==mx)nowans+=col[x];
	for(int i=head[x];i;i=nt[i])
		if(to[i]!=fa&&to[i]!=Son)ADD(to[i],x,val);
}
void dfs2(int x,int fa,int opt)
{
	for(int i=head[x];i;i=nt[i])
		if(to[i]!=fa&&to[i]!=son[x])dfs2(to[i],x,0);
	if(son[x])dfs2(son[x],x,1),Son=son[x];
	ADD(x,fa,1);Son=0;ans[x]=nowans;
	if(!opt)ADD(x,fa,-1),nowans=0,mx=0;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i)scanf("%d",&col[i]);;
	for(int i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs1(1,0);dfs2(1,0,1);
	for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
	return 0;
}