解题思路:
注意事项:
参考代码:
#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;
}
0.0分
8 人评分
C语言考试练习题_一元二次方程 (C语言代码)浏览:737 |
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)浏览:524 |
C语言程序设计教程(第三版)课后习题8.2 (C语言代码)浏览:5232 |
简单的for循环浏览:1411 |
WU-陶陶摘苹果2 (C++代码)浏览:975 |
水仙花 (C语言代码)浏览:1053 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:600 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:675 |
简单的a+b (C语言代码)浏览:647 |
C语言程序设计教程(第三版)课后习题4.9 (Java代码)浏览:613 |