Codeforces 600E :Lomsat gelral（启发式合并）

传送门

题意：
给一棵树，每个点有一个颜色，定义一个点的权值为其子树中最多的颜色（若有多个则是他们的和），求每个点的权值。

题解：

好题

首先可以Splay启发式合并一波，可以得到理论上的 O(nlogn) 复杂度，不过有一种跑得飞快的启发式合并方法，（实际复杂度也是 O(nlogn) 的）。

考虑对这棵树树链剖分。显然一个节点会贡献给所有的祖先，那么考虑先处理一个节点的所有轻儿子，再处理重儿子，把重儿子的信息保留，轻儿子的删除，然后再暴力重新统计一遍轻儿子即可。

为什么是 O(nlogn) ？因为每个轻儿子的信息被删除或者加入当且仅当当前节点向其连了一条轻边，而链剖时一个节点到根只有 O(logn) 条轻边，所以可以做到 O(nlogn)

当然这个方法可以适用于很多处理子树信息的情况。所以可拓展性比较强，不过比较遗憾的是其不支持修改。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int rd(){
char ch=getchar();int i=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=getchar();}
return i*f;
}
inline void W(ll x){
static int buf[50];
if(!x){putchar('0');return;}
if(x<0){putchar('-');x=-x;}
while(x){buf[++buf[0]]=x%10;x/=10;}
while(buf[0])putchar(buf[buf[0]--]+'0');
}
const int N=1e5+50;
int n,col[N],id[N],dfn[N],sze[N],son[N],ind;
int g[N],nt[N*2],v[N*2],cnt[N],mx,ec;
ll sum[N],ans[N];
inline void adde(int x,int y){nt[++ec]=g[x];g[x]=ec;v[ec]=y;}
inline void dfs(int x,int f){
    sze[x]=1;dfn[x]=++ind;id[ind]=x;
for(int j=g[x];j;j=nt[j])
if(v[j]!=f){
            dfs(v[j],x);
            sze[x]+=sze[v[j]];
if(!son[x]||(sze[son[x]]<sze[v[j]]))son[x]=v[j];
        }
}
inline void add(int c,ll &x){
    sum[cnt[c]]-=c;
    sum[++cnt[c]]+=c;;
if(mx==cnt[c])x+=c;
if(mx==cnt[c]-1)x=c,mx=cnt[c];
}
inline void del(int c){
    sum[cnt[c]]-=c;
    sum[--cnt[c]]+=c;
if(mx==cnt[c]+1&&!sum[mx])mx--;
}
inline void dfs2(int x,int f,bool keep){
for(int j=g[x];j;j=nt[j]){
if(v[j]!=son[x]&&v[j]!=f)dfs2(v[j],x,0);
    }
if(son[x])dfs2(son[x],x,1),ans[x]=ans[son[x]];
    add(col[x],ans[x]);
for(int j=g[x];j;j=nt[j]){
if(v[j]!=son[x]&&v[j]!=f){
for(int p=dfn[v[j]]+sze[v[j]]-1;p>=dfn[v[j]];p--)
                add(col[id[p]],ans[x]);
        }
    }
if(!keep)
for(int p=dfn[x]+sze[x]-1;p>=dfn[x];p--)del(col[id[p]]);
}
int main(){
    n=rd();
for(int i=1;i<=n;i++)col[i]=rd();
for(int i=1;i<n;i++){
int x=rd(),y=rd();
        adde(x,y);adde(y,x);
    }
    dfs(1,0);
    dfs2(1,0,1);
for(int i=1;i<=n;i++)W(ans[i]),putchar('\n');
}