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

时间限制: 1s 内存限制: 256MB 提交: 3315 解决: 787
题目描述
给定一棵树，结点由 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 。 



                
                
                

                                        

                        
                        

                                                            
                                
                                                        
                            
                            
                            
                        

                    

                

                


                

            

            

                

                    

                        
比赛公告

                    

                    

                        

                            
认真完成集训任务，积极备战25年蓝桥杯比赛。勇敢冲刺，争取省一。加油。
                        

                    

                

                

                    

                        
比赛状况