「Codeforces 600F」Lomsat gelral

发表于

给定一棵 nn 个点的有根树，每个点有一种颜色。对于每个点，统计子树里出现次数最多的颜色（可能有多个）的编号和。

Constraints

n≤105n \leq 10^5

Solution

突然想起来 dsu on tree 还没有学，顺手补道模板题。

原理大概是：先统计轻儿子的答案，再消除轻儿子影响；然后统计重儿子答案，不消除重儿子影响。

总复杂度 O(nlogn)O(nlogn) 。

Code

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int n,cnt,x,y,mx;
int c[N],t[N],sz[N],son[N],first[N];
LL sum,ans[N];
bool vis[N];
struct edge{int to,next;}e[N*2];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v){e[++cnt]=(edge){v,first[u]};first[u]=cnt;}
void dfs1(int x,int fa)
{
	sz[x]=1;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		dfs1(to,x);sz[x]+=sz[to];
		if(sz[to]>sz[son[x]])son[x]=to;
	}
}
void change(int x,int fa,int val)
{
	t[c[x]]+=val;
	if(val>0&&t[c[x]]>=mx)
	{
		if(t[c[x]]>mx)sum=0,mx=t[c[x]];
		sum+=c[x];
	}
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa||vis[to])continue;
		change(to,x,val);
	}
}
void dfs2(int x,int fa,bool heavy)
{
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa||to==son[x])continue;
		dfs2(to,x,0);
	}
	if(son[x])dfs2(son[x],x,1),vis[son[x]]=true;
	change(x,fa,1);ans[x]=sum;
	if(son[x])vis[son[x]]=false;
	if(!heavy)change(x,fa,-1),mx=sum=0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)c[i]=read();
	for(int i=1;i<n;i++)
	{
		x=read();y=read();
		ins(x,y);ins(y,x);
	}
	dfs1(1,-1);dfs2(1,-1,0);
	for(int i=1;i<=n;i++)printf("%lld ",ans[i]);
	return 0;
}