CF600E(dsu on tree)

题意:

给你一棵n个点的有根树，以1为根，每个点有一个颜色。对于一颗以v为根的子树，其出现次数最多的颜色，为dominating顶点v这个子树的颜色，可能有多个这样的颜色。求以n个顶点分别为根的子树中，dominating 的颜色和。

思路：

一个很好想的暴力思路就是，dfs n个点，统计该点为根的子树中出现的颜色次数。时间、空间都是O(N^2)的。
我们可以每次统计完一个点后清空cnt数组，将空间降到O(N)。

继续优化，很显然，某个点的ans应该与其所有孩子的ans有关，所以我们应该尽量将其孩子的信息给用上。

仔细想一下上面暴力的过程，我们会发现其实在清除的时候，最后一棵子树是没必要清的，我们可以把它对cntcnt数组的贡献一直传上去。于是我们想到了如果人为地使重儿子是最后一棵子树的话，岂不美哉。于是我们在dfsdfs时最后访问重儿子就行了，然后复杂度就被优化到O(nlogn)了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;

int n,col[maxn];
vector<int> G[maxn];
ll ans[maxn];
int sz[maxn],son[maxn],cnt[maxn];
void dfs1(int u,int f){//get son 重孩子
    sz[u]=1;
    for(auto v : G[u]){
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]]) son[u]=v;
    }
}
bool vis[maxn];
int maxv;
ll sum;
//计算贡献
void calc(int u,int f,int k){//k的取值为1，-1分别对应累加和清楚

    cnt[col[u]] += k;//把当前节点的颜色累加到cnt中，+1|-1
    if(k>0 && cnt[col[u]]>=maxv){//更新答案
        if(cnt[col[u]] > maxv) sum=0,maxv=cnt[col[u]];
        sum += col[u];
    }
    for(int v : G[u]){
        if(v!=f && !vis[v]) calc(v,u,k);//递归计算子节点，vis表示点v已经计算过了
    }
}
void dfs2(int u,int f,int keep){//keep为1表明当前节点在重儿子的子树中，需要保留答案
    for(int v : G[u]){
        if(v!=f && v!=son[u]) dfs2(v,u,0);// 先dfs轻儿子
    }
    if(son[u]){      //再dfs重儿子
        dfs2(son[u],u,1);
        vis[son[u]] = 1;//标记重儿子
    }
    calc(u,f,1);//合并轻儿子和重儿子的数据
    ans[u]=sum;
    if(son[u]) vis[son[u]]=0;//取消标记
    if(!keep) calc(u,f,-1),sum=maxv=0;//清楚轻儿子
}
int main(){
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&col[i]);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(1,0);
    dfs2(1,0,0);
    for(int i=1;i<=n;i++) cout<<ans[i]<<' '; puts("");
    return 0;
}