I. 黄金树
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

故事发生在交界地。

黄金律法维持着交界地的秩序。"黑刀之夜"却造成了黄金律法的崩溃。

作为一名褪色者,你需要去集齐所有大卢恩,重建新的律法。

黄金树,以及黄金树笼罩之下的交界地

但是在此之前,你打算先去升级一下你的血瓶,以提高你的回血量。

升级血瓶,需要用到黄金树露滴。而黄金树露滴,产自黄金树。

黄金树是一棵由 $$$n$$$ 个节点组成的有根树,节点分别编号为 $$$1 \sim n$$$。其中,黄金树之根的编号为 $$$1$$$。

黄金树的每个节点,每天都能产出一定数量的黄金树露滴。

我们记节点 $$$i$$$($$$1 \leq i \leq n$$$)在第 $$$d$$$ 天($$$d \geq 0$$$)的产出效率为 $$$P[i][d]$$$。

然而,随着黄金律法的衰弱,黄金树产出黄金树露滴的能力也在逐渐减弱。

在第 $$$0$$$ 天,所有节点的产出效率都为正整数。之后,每过 $$$1$$$ 天,都会有部分节点的产出效率发生减小。

具体来讲,在第 $$$d$$$ 天,如果某个节点 $$$i$$$ 满足以下两个条件之一:

  • 节点 $$$i$$$ 是黄金树之根。
  • 节点 $$$i$$$ 不是黄金树之根,且该节点的产出效率大于其父亲节点的产出效率。

那么,在第 $$$d+1$$$ 天,其产出效率就会减 $$$1$$$(最多减少到 $$$0$$$)。否则,其产出效率将保持不变。

形式化的,我们用 $$$fa[i]$$$ 表示节点 $$$i$$$ 的父亲节点,则有:

$$$$$$ P[i][d+1] = \begin{cases} \max (0, P[i][d]-1) & \text{ , if } i = 1 \text{ or } P[i][d] \gt P[fa[i]][d] \\ P[i][d] & \text{ , else} \end{cases} $$$$$$

你非常关心你的血瓶的升级,因此你想知道,自己分别还能从每个节点那里收集到多少个黄金树露滴。

因此,请你对于每个节点 $$$i$$$,计算 $$$ \sum \limits_{d = 0}^{+\infty} P[i][d] $$$ 的值。

可以证明,其必定是一个有限的非负整数。

Input

本题的输入包含多组测试数据。

输入的第一行包含 $$$1$$$ 个整数 $$$T$$$($$$1 \leq T \leq 10^4$$$),表示一共有 $$$T$$$ 组测试数据。

对于每组测试数据:

输入的第一行包含 $$$1$$$ 个整数 $$$n$$$($$$2 \leq n \leq 10^6$$$),表示黄金树的节点个数。

输入的第二行包含 $$$n$$$ 个整数 $$$P[1][0], P[2][0], P[3][0], \cdots , P[n][0]$$$($$$1 \leq P[i][0] \leq 10^9$$$),用空格分隔,$$$P[i][0]$$$ 表示节点 $$$i$$$ 在第 $$$0$$$ 天的产出效率。

输入的第三行包含 $$$n-1$$$ 个整数 $$$fa[2], fa[3], fa[4], \cdots fa[n]$$$($$$1 \leq fa[i] \leq n$$$),用空格分隔,$$$fa[i]$$$ 表示节点 $$$i$$$ 的父亲节点编号。

输入数据保证 $$$n$$$ 个节点一定构成一棵有根树。

保证测试数据的 $$$n$$$ 的总和不超过 $$$10^6$$$ 。

Output

对于每组测试数据:

输出一行,包含 $$$n$$$ 个整数,用空格分隔,第 $$$i$$$ 个整数表示节点 $$$i$$$ 的答案。

Example
Input
6
5
2 1 2 1 5
1 1 2 2
6
8 4 5 7 7 6
1 1 3 2 4
5
7 2 1 3 1
1 2 3 4
4
7 6 7 9
1 2 3
10
19 31 26 8 5 26 48 24 24 8
1 6 2 1 8 8 1 5 7
2
1000000000 1
1
Output
3 3 5 4 15 
36 30 35 43 40 48 
28 15 9 13 11 
28 33 40 51 
190 496 377 228 90 351 1176 300 300 364 
500000000500000000 1000000001 
Note

在样例的第一组测试数据中:

节点每一天的产出效率总和
$$$1$$$$$$[2, 1, 0, 0, 0, 0, \cdots]$$$$$$3$$$
$$$2$$$$$$[1, 1, 0, 0, 0, 0, \cdots]$$$$$$3$$$
$$$3$$$$$$[2, 2, 1, 0, 0, 0, \cdots]$$$$$$5$$$
$$$4$$$$$$[1, 1, 1, 0, 0, 0, \cdots]$$$$$$4$$$
$$$5$$$$$$[5, 4, 3, 2, 1, 0, \cdots]$$$$$$15$$$