#P18337. Bitter

Bitter

Bitter

Melon Usk 接管了 Bitter 公司,并打算缩减员工数量。为此,他希望了解哪些员工的团队彼此相似。

公司管理结构是一棵有根树,员工编号为 1,…,n1,\ldots,n。员工 11 是 Melon;其余每名员工恰有一名直属上司,最终都由 Melon 管理。每名员工的直属下属有明确顺序,这个顺序很重要。 员工 vv 负责的项目为 pvp_v。

员工 vv 的团队 TvT_v 包括 vv 本人,以及直接或间接向 vv 汇报的所有员工。若负责某个项目 pp 的全部员工都在 TvT_v 中,就称这个项目由 vv 拥有。记 vv 拥有的项目集合为 OvO_v。

最初,Melon 希望两个团队的管理结构和对应员工的项目完全一致。但这样的相似员工太少,于是他允许在比较时,对团队拥有的项目进行一致的重命名。

形式化地,考虑两个员工 x,yx,y,选择一个双射

f:Ox⟶Oy.f:O_x\longrightarrow O_y.

把 TxT_x 中所有满足 pv∈Oxp_v\in O_x 的员工的项目,统一从 pvp_v 改成 f(pv)f(p_v);其它项目保持原来的编号。若经过这次变换,TxT_x 与 TyT_y 完全相同,就称 x,yx,y 相似。

这里的“完全相同”要求存在团队员工之间的双射 gg:根对应根,对应员工的项目相同,并且任意员工的第 jj 个孩子都对应到另一名员工的第 jj 个孩子。不能交换孩子的顺序。

重命名必须是双射:同一个拥有的项目必须始终改成同一个项目,不同拥有的项目必须改成不同项目;不拥有的项目不能重命名。如果 x≠yx\ne y,两个团队不作改动就完全相同,那么它们拥有的项目集合均为空,按定义它们仍然相似。

对每名员工 vv,求有多少名其它员工与他相似。

输入格式

第一行包含测试用例数 ZZ。

每组测试用例的第一行包含员工数 nn。

第二行包含 nn 个整数 p1,…,pnp_1,\ldots,p_n,表示每名员工负责的项目。

接下来 nn 行描述下属关系。第 ii 行先给出整数 did_i,表示员工 ii 的直属下属数量,随后给出这 did_i 名下属的编号,依次表示第一个、第二个,直到第 did_i 个孩子。

输入保证构成一棵以员工 11 为根的树。员工编号不代表先序或后序次序。

输出格式

对每组测试用例输出一行 nn 个整数 c1,…,cnc_1,\ldots,c_n。cvc_v 是与员工 vv 相似、且不同于 vv 的员工数量。

数据范围

  • 1≤Z≤1000001\le Z\le100000;
  • 1≤n≤4000001\le n\le400000;
  • 1≤pv≤n1\le p_v\le n;
  • 0≤di<n0\le d_i<n;
  • 每个下属编号均在 1,…,n1,\ldots,n 之间;
  • 所有测试用例的员工总数不超过 800000800000。

样例输入 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

样例说明

样例示意图如下,不同颜色表示不同项目。孩子从左到右的顺序对应输入中的顺序。

Bitter 样例管理树,不同颜色代表不同项目

相似的员工对恰为:

$$(2,7),(4,5),(6,11),(9,10),(12,15),(13,16),(14,17),(19,20).$$

员工 3,83,8 不相似,因为它们在一个项目上不同,而这两个项目分别都不由 3,83,8 拥有。不过它们由更上方的 2,72,7 拥有,因此比较 2,72,7 时可以作项目重命名,使两个团队相同。

员工 1818 不与任何其它员工相似:它拥有三个项目,而其它管理结构相同的团队至多拥有一个项目,无法建立要求的双射。

没有下属的两名员工,在以下任一情形下相似:各自都拥有自己负责的项目,或者负责的项目编号相同。样例中的 19,2019,20 属于前一种情形,4,54,5 等员工对属于后一种情形。