CF600E Lomsat gelral

Description

对每个结点求所有在子树中的数的众数。如果有多个，保留它们的和。

。

Sol

DSU on Tree 板子。

DSU on Tree 是一个非常好用的处理子树问题的Trick。其基本流程如下：

找到重儿子
算出其他轻儿子的答案，清空
算出重儿子的答案，不清空
将其他轻儿子的答案并到重儿子上

时间复杂度证明：每个结点被计算的次数就是其到根路径上的轻边数，而在树剖已经证明过一个点到根的轻边数是级的，因此时间复杂度并且大部分时候卡不满于是拥有极其优秀的常数。

这道题直接照着基本流程做就好了。

Code

#include<bits/stdc++.h>
#define int long long
using std::vector;
typedef vector<int> vi;
typedef long long ll;
template<typename Tp=int>inline Tp read(){Tp x(0);int op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}

signed main(){
    int n=read();
    vi a(n+1);
    vector<vi> G(n+1);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<n;++i){
        int u=read(),v=read();
        G[u].push_back(v),G[v].push_back(u);
    }
    vi siz(n+1),son(n+1),buc(n+1);
    vector<ll> ans(n+1);
    std::function<void(int,int)> gson=[&](int u,int f){
        siz[u]=1;
        for(auto v:G[u])if(v!=f){
            gson(v,u);
            siz[u]+=siz[v];
            if(siz[son[u]]<siz[v])son[u]=v;
        }
    };//计算子树大小和重儿子
    vi use;
    ll cur=0,maxn=0;
    std::function<void(int,int)> dfs=[&](int u,int f){
        auto add=[&](int x){
            use.push_back(a[x]);
            buc[a[x]]++;
            if(buc[a[x]]>maxn)cur=a[x],maxn=buc[a[x]];
            else if(buc[a[x]]==maxn)cur+=a[x];
        };//增加贡献
        auto clr=[&](){
            for(auto v:use)buc[v]=0;
            cur=maxn=0;
            use.clear();
        };//清空
        std::function<void(int,int)> df=[&](int u,int f){//统计子树贡献
            add(u);
            for(auto v:G[u])if(v!=f)df(v,u);
        };
        for(auto v:G[u])if(v!=f&&v!=son[u])dfs(v,u),clr();//dfs轻儿子并清空
        if(son[u])dfs(son[u],u);//dfs重儿子不清空
        for(auto v:G[u])if(v!=f&&v!=son[u])df(v,u);//把轻儿子的答案并到重儿子上
        add(u),ans[u]=cur;//记得加结点本身的贡献
    };gson(1,0),dfs(1,0);
    for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
    return 0;
}