P9233
scallion
2023-04-30 18:49:01
### 题意
给定一棵树，求有多少棵子树：出现过的颜色出现次数均相等。
$n\leq2\times{10}^5$
### 做法
yt 说：“要用树上启发式合并。”于是这题我们就用了树上启发式合并。
一看子树颜色就感觉很板，然后颜色出现次数均相等就需要记录 $\min$ 和 $\max$ ，判断是否相等即可。而记录 $\min$ $\max$ 只需要开两个桶，每次加点删点的时候更新。
然后这题唯一有一点细节是：我们维护的是出现过的最小值，即不会等于 0。那么我们在对一种颜色进行 $add$ 的时候，它可能在此前没有出现，然后变成新的最小值。
时间复杂度 $O(n\log n)$ 。
### 代码
```cpp
#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;
}