P9233 颜色平衡树

从树上启发式合并找到的题，所以就讲讲树上启发式合并这个做法吧。

meaning

给定一棵树，求有多少棵子树，满足出现过的颜色出现次数均相等。

solve

此处默认了解过树上启发式合并。

这个题目一看就很板，实际上这就是个模板题。我们需要记录颜色出现次数均相等，直接记录每种颜色出现次数显然不大可能，但我们换个思路，话说每种颜色出现次数均相等，不就意味着出现的最多次数等于出现的最少次数吗？所以我们只需记录出现颜色次数的

min

值和

max

值，判断是否相等即可。

至于怎么记录，开两个数组即可，一个是记录颜色个数，一个是记录权值出现次数。

可能有些细节实现需要注意，具体细节看代码，大致思路就到这里。

code

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
struct node{
	int next,to;
}e[N];
int n,cnt,ans,imax,imin;
int head[N],siz[N],son[N],col[N],num1[N],num2[N];
void add(int u,int v)
{
	e[++cnt]={head[u],v};
	head[u]=cnt;
}
void add(int x)
{
	num2[num1[x]]--;
	num1[x]++;
	num2[num1[x]]++;
	if(num1[x]<imin) imin=num1[x];
	if(num1[x]>imax) imax=num1[x];
	if(!num2[imin]) imin++;
}
void del(int x)
{
	num2[num1[x]]--;
	num1[x]--;
	num2[num1[x]]++;
	if(num1[x]&&num1[x]<imin) imin=num1[x];
	if(!num2[imax]) imax--;
}
void dfs1(int u)
{
	siz[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		dfs1(v);
		if(siz[v]>siz[son[u]]) son[u]=v;
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int sign)//绝对没有人像我一样傻呵呵地以为sign=0可以不递归吧
{                        //真服了自己当时神奇的脑回路，忍不住记一下，笑死
	if(sign) add(col[u]);
	else del(col[u]);
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		dfs2(v,sign);
	}
}
void dfs3(int u)
{
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==son[u]) continue;
		dfs3(v);
		dfs2(v,0);
	}
	if(son[u]) dfs3(son[u]);//勿忘
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==son[u]) continue;
		dfs2(v,1);
	}
	add(col[u]);//勿忘
	if(imin==imax) ans++;
}
int main()
{
	cin>>n;
	for(int i=1,fa;i<=n;i++)
	{
		cin>>col[i]>>fa;
		add(fa,i);
	}
	dfs1(1);
	imin=1;//勿忘
	dfs3(1);
	cout<<ans<<endl;
	return 0;
}

题解：P9233 [蓝桥杯 2023 省 A] 颜色平衡树

文章操作