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

Mu会选择一颗星星作为焦点,并把望远镜的焦距调到某个整数d()。此时能看见的,恰好是与焦点距离不超过d的全部星星。
每颗星星i的可见度 初始为0。Mu拥有一些滤镜:滤镜(i,x)仅作用于第i颗星星,安装后将其可见度变为 ,其中 是按位异或。Mu可以任选拥有的滤镜并以任意顺序安装,也可以一个都不选;同一种滤镜可能有多份,可以选用多份相同的滤镜。
Mu希望所有处于视野中的星星可见度相等,并让这个共同值尽可能大。固定焦点后,令f(d)表示焦距为d时可以达到的最大共同可见度。不同焦点、不同d的最优值分别计算,可以各自选择滤镜,不要求同一套选择同时达到这些最优值。
对每颗星星作为焦点,求
输入格式
第一行一个整数n。
第二行n−1个整数 ,表示星星 与星星i+1之间有一条边。
接下来n行,第i行先给出整数 ,表示作用于星星i的滤镜数量;随后给出 个整数 。
输入只有一个测试用例。
输出格式
输出n行。第i行输出星星i作为焦点时的上述和,取模 ,使用范围 到 内的十进制非负整数表示。
数据范围
- 。
- ,给出的边连接全部星星。
- ,。
- 。
样例输入 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。