树上启发式合并裸题

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

#define maxn 200010

#define maxc 200010

int n;

int son[maxn],color[maxn],sz[maxn];//son[i]表示i的重儿子

int cnt[maxc];//cnt[i]表示颜色i出现的次数 

vector<int> tu[maxn];

int mx,tot;//mx是子树中颜色的最多的出现次数，tot是有多少种颜色达到了这个次数 

int ans; 

void dfs_son(int u){

sz[u]=1;

for(int v:tu[u]){

dfs_son(v);

if(sz[son[u]]<sz[v])son[u]=v;

sz[u]+=sz[v];

}

} 

void update(int u,int pson){

int c=color[u];

cnt[c]++;

if(mx<cnt[c])mx=cnt[c],tot=1;

else if(mx==cnt[c])tot++;

for(int v:tu[u]){

if(v==pson)continue;

update(v,-1);

}

}

void del(int u){

cnt[color[u]]--;

for(int v:tu[u])del(v);

}

void dfs(int u,int op){

for(int v:tu[u]){

if(v==son[u])continue;

dfs(v,0);

}

if(son[u])dfs(son[u],1);

update(u,son[u]);

if(mx*tot==sz[u])ans++;

if(!op){

del(u);

mx=0;tot=0;

}

}

int main(){

scanf("%d",&n);

int u,c;

for(int i=1;i<=n;i++){

scanf("%d%d",&c,&u);

tu[u].push_back(i);

color[i]=c;

}

dfs_son(1);

dfs(1,1);

printf("%d",ans);

return 0;

}