【dsu on tree】Codeforces600E[Lomsat gelral]題解

題目概述

給出一棵 n 個節點的樹，每個節點有一個顔色。如果 c 是一個節點子樹中出現次數最多的顔色，則稱該節點被 c 占領（一個節點可以被許多顔色占領）。求每個節點的 ∑c 。

解題報告

爛大街的dsu on tree（樹上啟發式合并）經典題。先樹剖，對于 x 我們遞歸求出輕兒子的答案（不記錄資訊），然後再求出重兒子的答案（記錄資訊）。之後暴力統計所有子樹節點的資訊（重兒子為根的子樹不需要再統計）求出 x 的答案，若 x 不需要保留資訊，則再将 x 子樹的資訊暴力抹去。

因為重兒子留着不删，是以就是父親以及輕兒子合并到重兒子的過程。由于所在子樹大小至少 ×2 ，是以顯然每個節點隻會被插入 log2n 次，效率 O(nlog2n) 。

示例程式

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=,maxe=maxn<<;

int n,col[maxn+],fa[maxn+];
int E,lnk[maxn+],son[maxe+],nxt[maxe+];
int si[maxn+],SH[maxn+];bool vis[maxn+];
int MAX,num[maxn+];LL sum,ans[maxn+];

#define Add(x,y) son[++E]=y,nxt[E]=lnk[x],lnk[x]=E
void Dfs(int x,int pre=)
{
    si[x]=;fa[x]=pre;
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre)
    {
        Dfs(son[j],x);si[x]+=si[son[j]];
        if (si[son[j]]>si[SH[x]]) SH[x]=son[j];
    }
}
void Update(int x,int f)
{
    if ((num[col[x]]+=f)>=MAX)  if (num[col[x]]>MAX)
        MAX=num[col[x]],sum=col[x]; else sum+=col[x];
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=fa[x])
        if (!vis[son[j]]) Update(son[j],f);
}
void Solve(int x,bool fl=true)
{
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=fa[x])
        if (son[j]!=SH[x]) Solve(son[j],false);
    if (SH[x]) Solve(SH[x],true),vis[SH[x]]=true;
    Update(x,);ans[x]=sum;if (SH[x]) vis[SH[x]]=false;
    if (!fl) Update(x,-),MAX=sum=;
}
int main()
{
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=;i<=n;i++) scanf("%d",&col[i]);
    for (int i=,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    Dfs();Solve();for (int i=;i<=n;i++) printf("%I64d ",ans[i]);
    return ;
}