New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2071: [蓝桥杯2023初赛] 颜色平衡树

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：756 通过：144
提交提交记录统计

题目描述

给定一棵树，结点由 1 至 n 编号，其中结点 1 是树根。树的每个点有一个颜色 Ci。
如果一棵树中存在的每种颜色的结点个数都相同，则我们称它是一棵颜色平衡树。
求出这棵树中有多少个子树是颜色平衡树。

输入格式

输入的第一行包含一个整数 n，表示树的结点数。
接下来 n 行，每行包含两个整数 Ci, Fi，用一个空格分隔，表示第 i 个结点的颜色和父亲结点编号。
特别地，输入数据保证 F1 为 0 ，也即 1 号点没有父亲结点。
保证输入数据是一棵树。
对于 30% 的评测用例，n≤200，Ci≤200 ；
对于 60% 的评测用例，n≤5000，Ci≤5000 ；
对于100% 的评测用例，1≤n≤200000，1≤Ci≤200000，0≤Fi<i 。

输出格式

输出一行包含一个整数表示答案。

输入样例 复制 

6
2 0
2 1
1 2
3 3
3 4
1 4

输出样例 复制 

4

数据范围与提示

编号为1, 3, 5, 6 的 4 个结点对应的子树为颜色平衡树。