CF 600 E 启发式合并

CF 600 E

Solution:

这是道启发式合并模板题.

所以要怎么启发式合并呢?

首先求出所有节点的重孩子,然后求这个节点及其子树内的答案时,先处理非重孩子子树的答案,然后清空,然后处理重孩子子树答案,不清空,继承到这里,然后再加上非重孩子子树答案.复杂度是和树链剖分一样的.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
const int MAXN=100000;
const int MAXM=200000;
int n;
int col[MAXN+10];
int fir[MAXN+10],nxt[MAXM+10],v[MAXM+10],tot;
void adde(int from,int to)
{
    ++tot;
    v[tot]=to;nxt[tot]=fir[from];
    fir[from]=tot;
}
int sz[MAXN+10],hson[MAXN+10],l[MAXN+10],r[MAXN+10],a[MAXN+10],dfstime;
void getsz(int u,int fa)
{
    sz[u]=1;l[u]=++dfstime;a[dfstime]=u;
for(int e=fir[u];e;e=nxt[e])
    {
if(v[e]==fa)continue;
        getsz(v[e],u);
        sz[u]+=sz[v[e]];
if(sz[hson[u]]<sz[v[e]])hson[u]=v[e];
    }
    r[u]=dfstime;
}
ll ans[MAXN+10],sum[MAXN+10];
int cnt[MAXN+10],t;
void add(int o)
{
    sum[++cnt[col[o]]]+=col[o];
if(sum[t+1])++t;
}
void del(int o)
{
    sum[cnt[col[o]]--]-=col[o];
if(!sum[t])--t;
}
void alladd(int o){for(int i=l[o];i<=r[o];++i)add(a[i]);}
void alldel(int o){for(int i=l[o];i<=r[o];++i)del(a[i]);}
void solve(int u,int fa)
{
for(int e=fir[u];e;e=nxt[e])
    {
if(v[e]==fa||v[e]==hson[u])continue;
        solve(v[e],u);
        alldel(v[e]);
    }
if(hson[u])solve(hson[u],u);
for(int e=fir[u];e;e=nxt[e])
    {
if(v[e]==fa||v[e]==hson[u])continue;
        alladd(v[e]);
    }
    add(u);
    ans[u]=sum[t];
}
int main()
{
    scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",col+i);
for(int i=1,u,v;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        adde(u,v);adde(v,u);
    }
    getsz(1,0);
    solve(1,0);
for(int i=1;i<=n;++i)printf("%lld ",ans[i]);
return 0;
}