题解 CF600E 【Lomsat gelral】

这是一道练启发式合并 （dsu on tree） 的好题

先简单说一下启发式合并吧

这道题我们可以遍历整棵树，并用一个数组ap（appear）记录每种颜色出现几次

但是每做完一棵子树就需要清空ap，以免对其兄弟造成影响。

而这样做它的祖先时就要把它重新搜一遍，浪费时间

但是我们发现，对于每个节点v，最后一棵子树是不用清空的，因为做完那棵子树后可 以把其结果直接加入v的答案中。

选哪棵子树呢？当然是所含节点最多的一棵咯，我们称之为“重儿子”

其实感觉这样快不了多少……但是它竟然是nlogn的！

对于这道题

先用一遍dfs算出每个点是否为重儿子

再dfs统计答案，每次碰到重儿子就跳过，递归完清空ap数组等东东

最后dfs重儿子，不清空

再对当前节点进行另一种dfs，暴力统计ap，不做重儿子

看代码吧~~~（这是帅的人最不关心的部分）

------------我是分割线

//written by YellowBean, the AKer of IMO (rubbish)
#include<bits/stdc++.h>
#define ll long long
#define re register
using namespace std;
const int N=2e5+10;
int n;
int c[N];//color
int v[N],nex[N],first[N],tot=1;
inline void add(int x,int y){
    v[++tot]=y;
    nex[tot]=first[x];
    first[x]=tot;
}
inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
}
ll ans[N],ap[N],mx,sum;//十年OI一场空，不开 long long 见祖宗 
//ap表示每种颜色出现几次 mx表示出现最多的次数 sum表示颜色编号和 
int sz[N];//子树大小 
bool gson[N];//表示一个点是否为重儿子 
void getg(int x,int f){//get 子树大小 以及 重儿子 
    sz[x]=1;
    int mx=0,p=0;
    for(re int i=first[x];i;i=nex[i]){
        int y=v[i];
        if(y==f)continue;
        getg(y,x);sz[x]+=sz[y];
        if(sz[y]>mx){
            mx=sz[y];
            p=y;
        }
    }if(p)gson[p]=1;
}
void DFS(int x,int f,int p){//暴力遍历子树 p为重儿子 之后需init清空 
    //统计答案 
    ap[c[x]]++;
    if(ap[c[x]]>mx){
        mx=ap[c[x]];
        sum=c[x];
    }else if(ap[c[x]]==mx)sum+=c[x];
    for(re int i=first[x];i;i=nex[i]){
        int y=v[i];
        if(y==f || y==p)continue;//不要把重儿子也一起遍历了！ 
        DFS(y,x,p);
    }
}
inline void init(int x,int f){//暴力遍历后清空 
    ap[c[x]]--;
    for(re int i=first[x];i;i=nex[i]){
        int y=v[i];
        if(y==f)continue;
        init(y,x);
    }
}
void dfs(int x,int f){//启发式合并关键函数！ 
    int p=0;//重儿子标记 
    for(re int i=first[x];i;i=nex[i]){
        int y=v[i];
        if(y==f)continue;
        if(!gson[y]){//不是重儿子的暴力做 
            dfs(y,x);
            init(y,x);
            sum=mx=0;
        }
        else p=y;
    }if(p)dfs(p,x);//重儿子单独特判
    DFS(x,f,p);
    ans[x]=sum;
}
int main(){
    n=read();
    for(re int i=1;i<=n;i++)c[i]=read();
    for(re int i=1;i<n;i++){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }getg(1,0);
    dfs(1,0);
    for(re int i=1;i<=n;i++)
        printf("%lld ",ans[i]);
}
//those who read but don't copy are handsome

关于复杂度证明：

对于每个节点，它被计算的次数就是它到根节点路径上的轻边（连到轻儿子的边）数

我们只需算出轻边有几条

由于每从一个深度为d的节点沿一条轻边走到深度（d-1）的节点，子树大小就至少*2 （这是因为有一个重儿子>=当前子树）

所以最多只有logn条轻边！

故复杂度为O（nlogn）！

皆大欢喜！