#P18590. Vulpecula

Vulpecula

Vulpecula

Mu喜欢在夜晚用望远镜观察小狐狸星座Vulpecula。他把星座建模为一棵树:有n颗编号为1到n的星星,以及连接它们的n−1条线,任意两颗星星之间都连通。两颗星星的距离定义为树上路径的边数。

原题中的Vulpecula星座示意

Mu会选择一颗星星作为焦点,并把望远镜的焦距调到某个整数d(0≤d≤n−10\le d\le n-1)。此时能看见的,恰好是与焦点距离不超过d的全部星星。

每颗星星i的可见度 aia_i 初始为0。Mu拥有一些滤镜:滤镜(i,x)仅作用于第i颗星星,安装后将其可见度变为 ai⊕xa_i\oplus x,其中 ⊕\oplus 是按位异或。Mu可以任选拥有的滤镜并以任意顺序安装,也可以一个都不选;同一种滤镜可能有多份,可以选用多份相同的滤镜。

Mu希望所有处于视野中的星星可见度相等,并让这个共同值尽可能大。固定焦点后,令f(d)表示焦距为d时可以达到的最大共同可见度。不同焦点、不同d的最优值分别计算,可以各自选择滤镜,不要求同一套选择同时达到这些最优值。

对每颗星星作为焦点,求

∑d=0n−1f(d)(mod264).\sum_{d=0}^{n-1} f(d)\pmod{2^{64}}.

输入格式

第一行一个整数n。

第二行n−1个整数 p1,p2,…,pn−1p_1,p_2,\ldots,p_{n-1},表示星星 pip_i 与星星i+1之间有一条边。

接下来n行,第i行先给出整数 mim_i,表示作用于星星i的滤镜数量;随后给出 mim_i 个整数 xi,1,…,xi,mix_{i,1},\ldots,x_{i,m_i}。

输入只有一个测试用例。

输出格式

输出n行。第i行输出星星i作为焦点时的上述和,取模 2642^{64},使用范围 00 到 1844674407370955161518446744073709551615 内的十进制非负整数表示。

数据范围

  • 2≤n≤5×1042\le n\le5\times10^4。
  • 1≤pi≤i1\le p_i\le i,给出的边连接全部星星。
  • mi≥0m_i\ge0,∑imi≤2×106\sum_i m_i\le2\times10^6。
  • 0≤xi,j<2640\le x_{i,j}<2^{64}。

样例输入 1

2
1
2 2 3
2 1 1

样例输出 1

4
2

样例输入 2

5
1 2 2 3
3 83 75 58
4 125 124 58 16
4 39 125 71 112
3 69 66 5
4 48 73 69 6

样例输出 2

171
125
183
142
243

样例说明

第一组样例,以星星1为焦点,d=0时只需让星星1可见度达到3;d=1时,两颗星星可共同达到1。因此第一行答案为3+1=4。