dsu on tree

正好看到某up主講了這個就學習一下，up主視訊：不分解的AgOH

主要用于解決樹上無修改區間衆數類問題，比較典型的：CF 600E

證明：自為風月馬前卒

算法的主要流程為：

預處理出重兒子

所有子樹共享一個記錄顔色數量的數組

1. 對于每個點優先計算其輕兒子子樹内部的答案，并在回溯的時候将輕兒子及其自身所包含的子樹的顔色資訊删除。
2. 然後計算重兒子其子樹内部的答案，并且保留重兒子及其子樹的顔色資訊。
3. 然後暴力将所有輕兒子的所有資訊加入到顔色數組中，計算答案。

由于一些輕重鍊剖分中的一些性質，使得總的複雜度在 O ( n ∗ l o g 2 n ) O(n*log_2n) O(n∗log2​n)，這個我不會證，當時沒有好好學習樹鍊剖分的證明233。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e5+7;
struct Edge{
    int v,next;
}edge[maxn<<1];
int head[maxn],top;
void init(int n){
    top=0;
    memset(head,-1,sizeof(int)*n);
}
void add(int u,int v){
    edge[top].v=v;
    edge[top].next=head[u];
    head[u]=top++;
}
int col[maxn];
int siz[maxn],son[maxn];

void dfs(int u,int fa){
    int maxx=0;
    siz[u]=1;
    int v;
    for(int i=head[u];i!=-1;i=edge[i].next){
        v=edge[i].v;
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxx){
            maxx=siz[v];
            son[u]=v;
        }
    }
}
int Son,W[maxn];
ll sum;
int maxx;
void countt(int u,int fa,int val){
    col[W[u]]+=val;
    if(col[W[u]]>maxx) maxx=col[W[u]],sum=W[u];
    else if(col[W[u]]==maxx) sum+=W[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa||v==Son) continue;
        countt(v,u,val);
    }
}
void del(int u,int fa){
    --col[W[u]];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        del(v,u);
    }
}
ll ans[maxn];
void calc(int u,int fa,bool f){
    int v;
    for(int i=head[u];i!=-1;i=edge[i].next){//計算輕兒子的子樹對輕兒子的貢獻;
        v=edge[i].v;
        if(v==fa||v==son[u]) continue;
        calc(v,u,false);
    }
    if(son[u]) calc(son[u],u,true),Son=son[u];//計算重兒子的子樹對重兒子的貢獻;
    countt(u,fa,1);//将輕兒子及其子樹資訊加入到總顔色數組計算u節點的所有資訊;
    Son=0,ans[u]=sum;

    if(!f) del(u,fa),sum=0,maxx=0;//若u節點為輕兒子則删除所有資訊,否則保留資訊;
}

int main(){
    int n,u,v;
    scanf("%d",&n);
    init(n+2);
    for(int i=1;i<=n;++i) scanf("%d",&W[i]);
    for(int i=1;i<n;++i){
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs(1,0);
    maxx=0,sum=0;
    calc(1,0,1);
    for(int i=1;i<=n;++i) printf("%I64d ",ans[i]);
    return 0;
}