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

lzt415 · 2025-07-19 19:35:39 · 题解

P9233 颜色平衡树

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

meaning

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

solve

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

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

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

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

code

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