P9233

· · 题解

题意

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

n\leq2\times{10}^5

做法

yt 说：“要用树上启发式合并。”于是这题我们就用了树上启发式合并。

一看子树颜色就感觉很板，然后颜色出现次数均相等就需要记录 \min 和 \max ，判断是否相等即可。而记录 \min \max 只需要开两个桶，每次加点删点的时候更新。

然后这题唯一有一点细节是：我们维护的是出现过的最小值，即不会等于 0。那么我们在对一种颜色进行 add 的时候，它可能在此前没有出现，然后变成新的最小值。

时间复杂度 O(n\log n) 。

代码


#include<bits/stdc++.h>
using namespace std;
int n,num_edge,ans,mi,ma;
struct Edge{
    int to,next;
}e[400010];
int head[200010];
int a[200010];
int siz[200010];
int son[200010];
int t[2][200010];
void add_edge(int from,int to){
    e[++num_edge].to=to;
    e[num_edge].next=head[from];
    head[from]=num_edge;
}
void add(int x){
    t[1][t[0][x]]--;
    t[0][x]++;
    t[1][t[0][x]]++;
    if(t[0][x]<mi) mi=t[0][x];
    if(t[0][x]>ma) ma=t[0][x];
    if(!t[1][mi]) mi++;
}
void del(int x){
    t[1][t[0][x]]--;
    t[0][x]--;
    t[1][t[0][x]]++;
    if(t[0][x]&&t[0][x]<mi) mi=t[0][x];
    if(!t[1][ma]) ma--;
}
void dfs0(int u){
    int v;
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next){
        v=e[i].to;
        dfs0(v);
        if(siz[v]>siz[son[u]]) son[u]=v;
        siz[u]+=siz[v];
    }
}
void dfs1(int u,int ty){
    int v;
    if(!ty) del(a[u]);
    else add(a[u]);
    for(int i=head[u];i;i=e[i].next){
        v=e[i].to;
        dfs1(v,ty);
    }
}
void dfs2(int u){
    int v;
    for(int i=head[u];i;i=e[i].next){
        v=e[i].to;
        if(v==son[u]) continue;
        dfs2(v);
        dfs1(v,0);
    }
    if(son[u]) dfs2(son[u]);
    for(int i=head[u];i;i=e[i].next){
        v=e[i].to;
        if(v==son[u]) continue;
        dfs1(v,1);
    }
    add(a[u]);
    if(mi==ma) ans++;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;i++){
        cin>>a[i]>>x;
        add_edge(x,i);
    }
    dfs0(1);
    mi=1;
    dfs2(1);
    cout<<ans;
    return 0;
}