题解 CF600E 【Lomsat gelral】

## 这是一道练启发式合并 （dsu on tree） 的好题 ### 先简单说一下启发式合并吧 这道题我们可以遍历整棵树，并用一个数组ap（appear）记录每种颜色出现几次 但是每做完一棵子树就需要清空ap，以免对其兄弟造成影响。 而这样做它的祖先时就要把它重新搜一遍，浪费时间 但是我们发现，对于每个节点v，最后一棵子树是不用清空的，因为做完那棵子树后可 以把其结果直接加入v的答案中。 选哪棵子树呢？当然是所含节点最多的一棵咯，我们称之为“重儿子” 其实感觉这样快不了多少……但是它竟然是nlogn的！ ### 对于这道题 先用一遍dfs算出每个点是否为重儿子 再dfs统计答案，每次碰到重儿子就跳过，递归完清空ap数组等东东 最后dfs重儿子，不清空 再对当前节点进行另一种dfs，暴力统计ap，不做重儿子 看代码吧~~~（这是帅的人最不关心的部分） ------------我是分割线 ```cpp //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）！ #### 皆大欢喜！