Lomsat gelral

标签：cnt int son fa gelral now mx Lomsat

Lomsat gelral
统计节点出现次数最多的颜色之和
概要：运用树链剖分，每次不用重新跑重儿子，从而将复杂度降低到nlogn

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int M=1e5+5;

int h[M],ne[M<<1],e[M<<1],tot;
void add(int from,int to) {
    e[++tot]=to;  ne[tot]=h[from];  h[from]=tot;
}

int siz[M],son[M];
void dfs(int now,int fa) {
    siz[now]=1;//这里不要忘了，不然树剖失败
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa)continue;
        dfs(to,now);
        siz[now]+=siz[to];
        if(siz[to]>siz[son[now]])son[now]=to;
    }
}

ll ans[M],sum;
int mx,a[M],cnt[M];
void calc(int now,int fa,int Son,int k) {//这个不需要在找一次的重儿子
    cnt[a[now]]+=k;
    if(cnt[a[now]]>mx)mx=cnt[a[now]],sum=a[now];
    else if(cnt[a[now]]==mx)sum+=a[now];
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa||to==Son)continue;
        calc(to,now,Son,k);
    }
}

void dus(int now,int fa,int k) {
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa||to==son[now])continue;
        dus(to,now,0);
    }
    if(son[now])dus(son[now],now,1);
    calc(now,fa,son[now],1);//计算答案
    ans[now]=sum;
    if(k==0)calc(now,fa,0,-1),sum=mx=0;
}

int main() {
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1,x,y;i<n;i++) {
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    dus(1,0,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
    return 0;
}

标签：cnt,int,son,fa,gelral,now,mx,Lomsat
From： https://www.cnblogs.com/basicecho/p/16995112.html