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;
}