树上启发式合并

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>a
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct E{
    int to,next;
}Edge[maxn<<1];
int tot,Head[maxn];
inline void AddEdge(int u,int v){
    Edge[tot].to=v;
    Edge[tot].next=Head[u];
    Head[u]=tot++;
}
int siz[maxn],son[maxn];
void dfs (int u,int f){//与重链剖分相同的写法找重儿子
    siz[u]=1;
    for (int i=Head[u];~i;i=Edge[i].next){
        int v=Edge[i].to;
        if (v==f) continue;
        dfs (v,u);
        siz[u]+=siz[v];
        if (siz[v]>siz[son[u]]){
            son[u]=v;
        }
    }
}
int col[maxn],cnt[maxn];//col存放某结点的颜色，cnt存放某颜色在“当前”子树的数量
long long ans[maxn],sum;//ans是答案数组，sum用于累加计算出“当前”子树的答案
int flag,maxc;//flag用于标记重儿子，maxc用于更新最大值
//TODO 统计某结点及其所有轻儿子的贡献
void count(int u,int f,int val){
    cnt[col[u]]+=val;//val为正为负可以控制是增加贡献还是删除贡献
    if (cnt[col[u]]>maxc){//找最大值
        maxc=cnt[col[u]];
        sum=col[u];
    }else if (cnt[col[u]]==maxc){
        sum+=col[u];
    }
    for (int i=Head[u];~i;i=Edge[i].next){
        int v=Edge[i].to;
        if (v==f||v==flag){
            continue;
        }
        count (v,u,val);
    }
}
//DSU on tree的板子
void dfs (int u,int f,bool keep){
    // 第一步搞轻儿子及其子树算其答案删除贡献
    for (int i=Head[u];~i;i=Edge[i].next){
        int v=Edge[i].to;
        if (v==f||v==son[u]){
            continue;
        }
        dfs (v,u,false);
    }
    //第二步，搞重儿子及其子树算其答案不删贡献
    if(son[u]){
        dfs (son[u],u,true);
        flag=son[u];
    }
    //第三步，暴力统计u及其所有轻儿子的贡献合并到刚算出的重儿子信息里（sum）
    count(u,f,1);
    flag=0;
    ans[u]=sum;
    //把需要删除贡献的删一删
    if (!keep){//如果u是轻儿子
        count(u,f,-1);//刚才 +1现在-1清除贡献
        sum=maxc=0;//sum,maxc置零
    }
}
int main ()
{
    memset(Head,-1,sizeof (Head));
    int n;
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>col[i];
    }
    for (int i=1,u,v;i<n;i++){
        cin>>u>>v;
        AddEdge(u,v);
        AddEdge(v,u);
    }
    dfs (1,0);
    dfs (1,0,0);
    for (int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}