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

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

时间限制: 2s 内存限制: 320MB 提交: 2822 解决: 642

题目描述

给定一棵树，结点由 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年第十三届决赛真题-卡牌
蓝桥杯2020年第十一届省赛真题-成绩分析
蓝桥杯2024年第十五届决赛真题-兔子集结
蓝桥杯2019年第十届国赛真题-大胖子走迷宫
蓝桥杯2019年第十届国赛真题-轨道炮