【模板】树上启发式合并 dsu on tree

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const int maxn=2e5+10;
int n;
int c[N],cnum[N],numc[N];
vector<int> s[N];
int idfn[N],l[N],r[N],dfn,sz[N],b[N];
// s[u] 与 u 直接相连的节点的集合。
// sz[u] 以 u 为根的子树的大小。
// b[u] u 的重儿子，u 可能无儿子。
// l[u] 以 u 为根的子树的 dfs 序的区间左端点，亦为其自身的 dfs 序。
// r[u] 以 u 为根的子树的 dfs 序的区间右端点。
// idfn[i] dfs 序为 i 的节点编号。
// dfs1 获得 dfs 序与重儿子。
void dfs1(int u)
{
	l[u]=++dfn,idfn[dfn]=u;
	sz[u]=1;
	for(auto v:s[u])
	{
		dfs1(v);
		sz[u]+=sz[v];
		if(!b[u]||sz[b[u]]<sz[v]) b[u]=v;
	}
	r[u]=dfn;
}
int ans[N],sum;
// add 添加节点 u 对代求值的影响。
void add(int u)
{
	u=c[u];
	cnum[u]++;numc[cnum[u]]++;
	numc[cnum[u]-1]--;
}
// del 删除节点 u 对代求值的影响。
void del(int u)
{
	u=c[u];
	cnum[u]--;numc[cnum[u]]++;
	numc[cnum[u]+1]--;
}
// dfs2 计算以 u 为根的子树上代求值关于节点的值，
// tp==0，表示不记录影响，tp==1,记录。
void dfs2(int u,int tp)
{
	//先计算其轻子树上待求量关于节点的值，但不记录其轻子树上的节点对待求量关于 u 的值的影响。
	for(int v:s[u]) if(b[u]!=v)
	dfs2(v,0);
	
	// 如果有重子树，则再计算 u 的重子树上待求量关于节点的值，并记录其重子树上的节点对待求量关于 u 的值的影响。
	if(b[u]) dfs2(b[u],1);
	
	// 添加节点本身的影响。
	add(u);
	
	// 通过 dfs 序枚举 u 的轻子树上的节点，并将其贡献加入待求量关 u 的值的计算中。
	for(int v:s[u]) if(b[u]!=v)
	rep(i,l[v],r[v]) add(idfn[i]);
	
	if(1ll*cnum[c[u]]*numc[cnum[c[u]]]==sz[u]) ans[u]=1;
	
	//  若当前节点 u 通过轻边与之父亲相连，则需暂时消除 x 对待求量关于其父亲的值的影响。
	if(!tp) rep(i,l[u],r[u]) del(idfn[i]);
}
void solve()
{
	cin>>n; int x;
	rep(i,1,n)
	{
		cin>>c[i]>>x;
		s[x].pb(i);
	}
	dfs1(1); dfs2(1,1);
	rep(i,1,n) sum+=ans[i];
	cout<<sum<<endl;
}
int main()
{
	IOS
	int t=1;
	while(t--) solve();
	return 0; 
}