题面 luogu(暂时无法查看)
一道树上启发式合并
首先跑一边dfs，找出父节点和重儿子（不知道的先看树剖）
因为数据范围，只能开一个记录颜色数量的数组。最优的办法是保留重儿子的情况。
然而还有一个问题：数组归零和统计答案每次是$O(n)$的，一共$O(n^2)$。于是我用了一个时间戳的优化（见代码，有说明）
记得开longlong
代码丑,大佬轻喷: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
using namespace std;
typedef long long ll;
int n;
struct Array{ //优化
int tme,a[100010],t[100010],maxsize;
ll sum; //t为上次更改时间，a为数量，time为目前时间，maxn为最大的数量，sum为最大的之和
void clear(){tme++,maxsize=sum=0;} //只要把时间戳++，两个统计最大的归零即可(O(1))。
void inc(int k){
if(t[k]!=tme)a[k]=0,t[k]=tme; //如果上次更改之后有归零，则归零
a[k]++;
if(a[k]>maxsize)sum=0,maxsize=a[k];
if(a[k]==maxsize)sum+=k;
}
ll ans(){return sum;}
}a;
int head[100010],nxt[200010],cnt,v[200010];
int c[100010],wson[100010],fa[100010],s[100010];
ll ans[100010];
void add(int U,int V){ //加边
nxt[++cnt]=head[U];
head[U]=cnt;
v[cnt]=V;
}
void dfs1(int now){ //找重儿子
s[now]=1;
wson[now]=0;
for(register int i=head[now];i;i=nxt[i])
if(v[i]!=fa[now]){
fa[v[i]]=now;
dfs1(v[i]);
s[now]+=s[v[i]];
if(s[v[i]]>s[wson[now]])wson[now]=v[i];
}
}
void dfs2(int now,Array& a){ //统计以now为根子树中的颜色数量。
a.inc(c[now]);
for(register int i=head[now];i;i=nxt[i])
if(v[i]^fa[now])dfs2(v[i],a);
}
void dfs3(int now,Array& a){ //核心代码
if(wson[now]==0){ //叶子节点
ans[now]=c[now];
a.inc(c[now]);
return;
}
for(register int i=head[now];i;i=nxt[i]){
if(v[i]!=fa[now]&&v[i]!=wson[now]){
dfs3(v[i],a);
a.clear();
}
}
dfs3(wson[now],a); //重儿子影响保留
for(register int i=head[now];i;i=nxt[i]){ //加上其它子树
if(v[i]!=fa[now]&&v[i]!=wson[now]){
dfs2(v[i],a);
}
}
a.inc(c[now]); //别忘了加上自己
ans[now]=a.ans();//统计答案
}
int main(int argc,char**argv){ //主程序没啥可讲
scanf("%d",&n);
for(register int i=1;i<=n;i++)scanf("%d",c+i);
for(register int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs1(1);
dfs3(1,a);
for(register int i=1;i<=n;i++)printf("%lld ",ans[i]);
return 0;
}