一道树上启发式合并的例题。
首先考虑暴力的做法。统计每一个子节点的信息，然后传到父节点。
我们发现这样做的复杂度是\(O(n^2)\)的。显然，复杂度是错误的。
我们考虑修改统计子节点的顺序。
重链剖分有一个很有意义的性质：一个点通向根的路径上的轻边的数量最多不会超过\(log_n\)。这利用重链剖分的性质可以轻松用反证法证明。
那么，依据这个性质，我们可以统计轻边、上传重边。这也就意味着，对于每一次访问，如果它是一条轻边，那么就把它的信息统计完了清空；如果是一条重边，那么把它的信息上传。
例如，我们现在有一个节点\(X\)，那么我们先计算它的所有轻节点，然后我们再计算它的重节点，最后将它除了重节点以外的地方都搜一遍，这样就获得了它的所有信息。
为什么这样做复杂度是对的呢？这就可以基于刚刚那个性质来证明了。具体地来说，一个节点会被清理信息，当且仅当它是一个节点下面的一个轻节点。也就是说，它被清空的次数就是它通向根的路径上轻边的数量。
由刚才那个性质可得，这个值是对数级的，所以复杂度是对的。
注意sm数组的tp的控制。
#include<iostream>
#include<cstdio>
struct ee{
int v;
int nxt;
}e[200005];
int h[100005],et=0;
inline void add(int U,int V){
e[++et]=(ee){V,h[U]};
h[U]=et;
}
int sn[100005],sz[100005],a[100005],cnt[100005];
bool kp[100005];
long long ans[100005];//ans表示每个节点的答案
long long sm[100005];//sn表示出现次数为cnt次的颜色值的和
int n;
inline void dfs1(int X,int FA){
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v!=FA){
dfs1(e[i].v,X);
}
}
sz[X]=1;
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v){
sz[X]+=sz[e[i].v];
if(sz[e[i].v]>sz[sn[X]]){
sn[X]=e[i].v;
}
}
}
}
int tp;
inline void rnw(int X,int FA,int V){
sm[cnt[a[X]]]-=a[X];
cnt[a[X]]+=V;
sm[cnt[a[X]]]+=a[X];
if(sm[tp+1]){
++tp;
}
if(!sm[tp]){
--tp;
}
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v!=FA&&!kp[e[i].v]){
rnw(e[i].v,X,V);
}
}
}
inline void dfs2(int X,int FA,int isSn){
for(int i=h[X];i;i=e[i].nxt){
if(e[i].v!=FA&&e[i].v!=sn[X]){
dfs2(e[i].v,X,0);
}
}
if(sn[X]){
dfs2(sn[X],X,1);
kp[sn[X]]=1;
}
rnw(X,FA,1);
kp[sn[X]]=0;
ans[X]=sm[tp];
if(!isSn){
rnw(X,FA,-1);
}
}
void init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
int u,v;
for(int i=1;i<n;++i){
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,0);
dfs2(1,0,1);
for(int i=1;i<=n;++i){
printf("%lld ",ans[i]);
}
}
int main(){
init();
return 0;
}