题目描述

有一颗 $n$ 个节点的有根树， 树上节点的编号从 $1$ 到 $n$， 且 $1$ 为根节点。最开始， 每个节点上都有一只蛤蟆。 在每一秒末， 蛤蟆都会从当前节点跳到其父亲节点上。 如果蛤蟆当前在 $1$ 号节点， 那么他就会跳出这棵树。

同时， 每个节点上都有一只水母。 如果以一只水母所在的节点为根节点的子树内有 $x$ 只蛤蟆， 那就会带给它 $a_x$ 的快乐度。 现在你想知道第 $0\sim n-1$ 秒时所有水母的快乐度之和。

由于森林里有很多树， 所以你需要对每棵树都求出答案。

输入格式

第一行一个正整数 $T$ 表示树的个数。

每棵树输入格式如下：

第一行一个正整数 $n$ 表示树的节点数。

第 $2$ 行 $n$ 个整数， 第 $i$ 个整数 $f_{i+1}$ 表示第 $i+1$ 号节点的父亲。

第 $3$ 行 $n+1$ 的整数表示 $a_0\sim a_{n}$。

输出格式

输出 $T$ 行。

对于节点数为 $n$ 的树， 输出 $n$ 个整数表示 $0\sim n-1$ 秒时所有水母的快乐度之和。

样例 1 输入

4
6
1 2 3 2 2
3 5 7 4 7 8 1
6
1 1 3 2 2
3 8 6 5 7 7 10
6
1 2 1 1 3
3 9 2 7 9 9 5
2
1
0 2 3

样例 1 输出

31 29 24 20 18 18 
45 30 20 18 18 18 
41 29 23 24 18 18 
5 2

样例 2

见下发文件中的 tree2.in, tree2.ans。

样例 3

见下发文件中的 tree3.in, tree3.ans。

样例 4

见下发文件中的 tree4.in, tree4.ans。

附加文件

tree.zip

数据范围

令 $\sum n$ 表示所有数据中 $n$ 的和。

对于 $100 \%$ 的数据， 满足 $1 \leq n, \sum n \leq 10^6,0 \leq a_i \leq 10^9,1\ leq f_i < i$。