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

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

时间限制: 3s 内存限制: 320MB 提交: 2738 解决: 613

题目描述

给定一棵树，结点由 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 。


标签
 
分享 
































上一题
下一题











通过率












统　计












解题报告











推荐题目








蓝桥杯2022年第十三届决赛真题-卡牌
蓝桥杯2024年第十五届省赛真题-好数
蓝桥杯2024年第十五届省赛真题-R 格式
蓝桥杯2022年第十三届省赛真题-刷题统计
蓝桥杯2022年第十三届省赛真题-修剪灌木