Dotcpp  >  编程题库  >  蓝桥杯2023年第十四届省赛真题-颜色平衡树
题目 3144:

蓝桥杯2023年第十四届省赛真题-颜色平衡树

时间限制: 3s 内存限制: 320MB 提交: 1314 解决: 286

题目描述

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

输入格式

输入的第一行包含一个整数 n ,表示树的结点数。
接下来 n 行,每行包含两个整数 Ci , Fi,用一个空格分隔,表示第 i 个结点的颜色和父亲结点编号。
特别地,输入数据保证 F1 为 0 ,也即 1 号点没有父亲结点。保证输入数据是一棵树。

输出格式

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

样例输入

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

样例输出

4

提示

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


对于 30% 的评测用例,n ≤ 200,Ci ≤ 200 ;
对于 60% 的评测用例,n ≤ 5000,Ci ≤ 5000 ;
对于所有评测用例,1 ≤ n ≤ 200000,1 ≤ Ci ≤ 200000,0 ≤ Fi < i 。


标签