dsu on tree跟冰茶祭有什么关系啊喂
dsu on tree的模板题

思想与解题过程

类似树链剖分的思路

先统计轻儿子的贡献，再统计重儿子的贡献，得出当前节点的答案后再减去轻儿子对答案的贡献

似乎很蠢

但是复杂度是\(O(nlogn)\)的，在没有修改的情况下，可以把树上莫队吊起来打

没了

代码实现

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int cnt,u[100100<<1],heason[100100],v[100100<<1],sz[100100],fir[100100],nxt[100100<<1],vis[100100];

long long val[100100],ans[100100],w_p[100100],sum,maxv,n;

void addedge(int ui,int vi){

    ++cnt;

    u[cnt]=ui;

    v[cnt]=vi;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

void change(int u,int f,int c){

    val[w_p[u]]+=c;

    if(c>0&&val[w_p[u]]>=maxv){

        if(val[w_p[u]]>maxv)

            maxv=val[w_p[u]],sum=0;

        sum+=w_p[u];

    }

    for(int i=fir[u];i;i=nxt[i]){

        if(v[i]==f||vis[v[i]])

            continue;

        change(v[i],u,c);

    }

}

void dfs1(int u,int f){

    sz[u]=1;

    for(int i=fir[u];i;i=nxt[i]){

        if(v[i]==f)

            continue;

        dfs1(v[i],u);

        sz[u]+=sz[v[i]];

        if(heason[u]==0||sz[heason[u]]<sz[v[i]])

            heason[u]=v[i];

    }

}

void dfs2(int u,int f,int islight){

    for(int i=fir[u];i;i=nxt[i]){

        if(v[i]==f||v[i]==heason[u])

            continue;

        dfs2(v[i],u,1);

    }

    if(heason[u]) dfs2(heason[u],u,0),vis[heason[u]]=1;

    change(u,f,1);

    ans[u]=sum;

    if(heason[u]) vis[heason[u]]=0;

    if(islight) change(u,f,-1),sum=maxv=0;

}

signed main(){

    scanf("%lld",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld",&w_p[i]);

    }

    for(int i=1;i<=n-1;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    dfs1(1,0);

    dfs2(1,0,0);

    for(int i=1;i<=n;i++)

        printf("%lld ",ans[i]);

    return 0;

}