题目描述

给你一棵 $n$ 个点的有根树，根为 $1$。每条边上有一个字符 $c \in \{0, 1\}$。$S_u$ 表示从根到 $u$ 的路径上每条边的字符依次写下来组成的字符串。保证每个节点向儿子的边上的字符互不相同。

对每个点 $u$，有一个价值 $val_u$ 和一个限制 $a_u$。
对每个点 $u$，如果点 $v$ 满足 $S_u$ 是 $S_v$ 的后缀，那么我们认为 $v$ 是 $u$ 的扩展点。

Alice 手里有一个字符串 $S = S_u$，现在她可以删掉若干末尾的字符，使得 $S$ 变成 $S'$，并将 $S'$ 告诉 Bob。

Bob 获得了一个字符串 $S'$，他需要在 $S'$ 之后加入若干字符，得到 $S''$。如果存在 $u$ 的某个扩展点 $v$，满足 $S'' = S_v$，并且 $|S'| \ge a_v$，那么 Bob 就获得了 $val_v$ 的收益。Bob 只能进行一次这样的操作，所以他会选择符合条件的 $v$ 里 $val_v$ 最大的那个。如果没有符合条件的 $v$，Bob 只能获得 $0$ 收益。

现在 Alice 想知道，对于删除 $0 \sim |S_u|$ 个字符，总计 $|S_u| + 1$ 种删除方式里 Bob 能获得权值之和是多少？

对于每个 $u$，你都需要回答 Alice 的询问。

形式化地说：
我们需要对每个点 $u$ 求出
$ ans_u = \sum_{i=0}^{|S_u|} \max_{\substack{i \ge a_v \\ S_u = S_v[|S_v|-|S_u|+1, |S_v|] \\ S_u[1, i] = S_v[1, i]}} val_v $

其中 $S[l, r]$ 表示字符串 $S$ 的第 $l$ 到第 $r$ 个字符组成的字符串。特殊的，$S[x+1, x]$ 表示空串。$|S|$ 表示字符串 $S$ 的长度，$\land$ 表示且。

---

输入格式

多组测试数据，第一行一个整数 $T$ 表示数据组数。

对于每组测试数据：

• 第一行一个正整数 $n$，表示节点个数。
• 接下来 $n - 1$ 行，每行两个整数 $fa_i, c_i$ 表示第 $i$ 个点的父亲编号，以及边上的字符。
• 接下来一行 $n$ 个正整数 $val_1, val_2, \dots, val_n$。
• 接下来一行 $n$ 个非负整数 $a_1, a_2, \dots, a_n$。

---

输出格式

输出一行 $n$ 个整数 $ans_1, ans_2, \dots, ans_n$。

---

样例

输入

1
5
1 0
1 1
2 0
2 1
1 2 3 4 5
0 1 0 1 2

输出

3 4 6 8 5

以下表格表示当 $u, i$ 固定时，式子中 $val_v$ 的最大值：

$u$ \ $i$	0	1	2
1	3
2	0	4
3
4	0	4
5		0	5

---

数据规模与约定

对于所有数据保证：

• $1 \le T \le 5$
• $1 \le n \le 5 \times 10^5$
• $1 \le val_i \le 10^9$
• $1 \le fa_i < i$
• $c_i \in \{0, 1\}$
• $0 \le a_i \le n$

具体测试点限制如下：

测试点编号	$n \le$	特殊性质
1~2	100
3~5	$2\times 10^3$
6~8	$10^4$
9~10	$10^5$	A
11~12		B
13~16
17~20	$5\times 10^5$

特殊性质 A：$c_i = 0$。
特殊性质 B：$fa_i = \lfloor \frac{i}{2} \rfloor$。