Codeforces 600E Lomsat gelral（dsu on tree树上启发式合并）

题意

给一颗有根树，节点有颜色，求每个点子树内出现次数最多的颜色的权值（有多个就是权值和）。

1 ≤ n ≤ 10⁵ 

1 ≤ ci ≤ n 权值

题解

考虑暴力的做法，对于每个节点直接遍历，将颜色放入桶，统计答案。这样复杂度是n²的。

怎么去优化呢？可以看到每次遍历完一棵子树，我们都是把桶清空再重新遍历，其实他的有些信息是可以保留的。

如何就出现了一种做法，对于整个树先dfs一遍找出每个点的重儿子（同树链剖分）

我们再遍历时，从根遍历，先进轻儿子所在子树，统计轻儿子的答案，然后将桶清除。

然后再进重儿子所在子树，统计重儿子答案，不清除桶。

接着再把轻儿子和他本身加入桶，统计答案。

看上去也很暴力，那为什么时间复杂度是对的呢？

遇到一条轻边，就会把整个子树加入一遍，对于每个点，他到根的轻边条数就是他被加入的次数，所以复杂度nlgn

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=100005;
int n;
int co[maxn];
int size[maxn],fa[maxn],son[maxn];
ll get_it[maxn],ans;
int cx[maxn],num;
vector<int>e[maxn];

void dfs(int u){
    size[u]=1;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs(v);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

void clear(int u){
    cx[co[u]]--;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        clear(v);
    }
}

void add(int u){
    cx[co[u]]++;
    if(cx[co[u]]>num) ans=co[u],num=cx[co[u]];
    else if(cx[co[u]]==num) ans+=co[u];
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]) continue;
        add(v);
    }
}

void get_ans(int u){
    if(!u) return ;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa[u]||v==son[u]) continue;
        get_ans(v);
        ans=0;num=0;
        clear(v);
        //for(int i=1;i<=n;i++) printf("%d ",cx[i]);
        //putchar(10);
    }
    get_ans(son[u]);
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==son[u]||v==fa[u]) continue;
        add(v);
    }
    cx[co[u]]++;
    if(cx[co[u]]>num) ans=co[u],num=cx[co[u]];
    else if(cx[co[u]]==num) ans+=co[u];
    get_it[u]=ans;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&co[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    get_ans(1);
    for(int i=1;i<=n;i++) printf("%I64d ",get_it[i]);
}