给出一棵有向树一共N(1 < N <= 1000)个节點,如果一个节点的度(入度+出度)不小于它所有儿子以及它父亲的度(如果存在父亲或儿子)则称这样的节点为p节点,现要求统计p节點的个数
每组数据第一行为N表示树的节点数,后面为N-1行每行两个数x,y(0 <= x,y <= N)代表y是x的儿子节点。
每组数据输出一行为一个整数,代表这棵树上p节点的个数
1、题目要求计算的度为入度和出度的和,度是图中的概念用邻接矩阵计算最为方便。且又因为在该题中箭头的方向不是关键(因为是入度+出度)可以直接将有向树转换为无向图,将度看作是权值这个问题又可以看作“最小堆”问题。只需在最尛堆问题的基础上考虑上父节点的度即可
2、先假设所有的节点都是p节点,一旦判断不符合p节点的条件就减一并跳出循环