#P18337. Bitter
Bitter
Bitter
Melon Usk 接管了 Bitter 公司,并打算缩减员工数量。为此,他希望了解哪些员工的团队彼此相似。
公司管理结构是一棵有根树,员工编号为 。员工 是 Melon;其余每名员工恰有一名直属上司,最终都由 Melon 管理。每名员工的直属下属有明确顺序,这个顺序很重要。 员工 负责的项目为 。
员工 的团队 包括 本人,以及直接或间接向 汇报的所有员工。若负责某个项目 的全部员工都在 中,就称这个项目由 拥有。记 拥有的项目集合为 。
最初,Melon 希望两个团队的管理结构和对应员工的项目完全一致。但这样的相似员工太少,于是他允许在比较时,对团队拥有的项目进行一致的重命名。
形式化地,考虑两个员工 ,选择一个双射
把 中所有满足 的员工的项目,统一从 改成 ;其它项目保持原来的编号。若经过这次变换, 与 完全相同,就称 相似。
这里的“完全相同”要求存在团队员工之间的双射 :根对应根,对应员工的项目相同,并且任意员工的第 个孩子都对应到另一名员工的第 个孩子。不能交换孩子的顺序。
重命名必须是双射:同一个拥有的项目必须始终改成同一个项目,不同拥有的项目必须改成不同项目;不拥有的项目不能重命名。如果 ,两个团队不作改动就完全相同,那么它们拥有的项目集合均为空,按定义它们仍然相似。
对每名员工 ,求有多少名其它员工与他相似。
输入格式
第一行包含测试用例数 。
每组测试用例的第一行包含员工数 。
第二行包含 个整数 ,表示每名员工负责的项目。
接下来 行描述下属关系。第 行先给出整数 ,表示员工 的直属下属数量,随后给出这 名下属的编号,依次表示第一个、第二个,直到第 个孩子。
输入保证构成一棵以员工 为根的树。员工编号不代表先序或后序次序。
输出格式
对每组测试用例输出一行 个整数 。 是与员工 相似、且不同于 的员工数量。
数据范围
- ;
- ;
- ;
- ;
- 每个下属编号均在 之间;
- 所有测试用例的员工总数不超过 。
样例输入 1
1
20
3 1 2 1 1 2 5 2 5 5 2 9 8 9 9 8 9 7 6 4
5 18 15 12 2 7
2 3 4
2 5 6
0
0
0
2 8 9
2 10 11
0
0
0
2 13 14
0
0
2 16 17
0
0
2 19 20
0
0
样例输出 1
0 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1
样例说明
样例示意图如下,不同颜色表示不同项目。孩子从左到右的顺序对应输入中的顺序。

相似的员工对恰为:
$$(2,7),(4,5),(6,11),(9,10),(12,15),(13,16),(14,17),(19,20).$$员工 不相似,因为它们在一个项目上不同,而这两个项目分别都不由 拥有。不过它们由更上方的 拥有,因此比较 时可以作项目重命名,使两个团队相同。
员工 不与任何其它员工相似:它拥有三个项目,而其它管理结构相同的团队至多拥有一个项目,无法建立要求的双射。
没有下属的两名员工,在以下任一情形下相似:各自都拥有自己负责的项目,或者负责的项目编号相同。样例中的 属于前一种情形, 等员工对属于后一种情形。