题目描述

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

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

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

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

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

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

形式化地说：

我们需要对每个点 $u$ 求出 $\mathit{ans}_u = \sum\limits_{0 \le i \le \lvert S_u \rvert} \max\limits_{i \ge a_v \land S_u = S_v[\lvert S_v \rvert - \lvert S_u \rvert + 1, \lvert S_v \rvert] \land S_u[1, i] = S_v[1, i]} \mathit{val}_v$。

特殊的，如果对于某个 $u$，不存在任何 $v$ 满足条件，那么 $\max = 0$。

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

输入格式

多组测试数据，第一行一个整数 $T$ 表示数据组数。
对于每组测试数据，第一行一个正整数 $n$，表示节点个数。
接下来 $n - 1$ 行，每行两个整数 $\mathit{fa}_i, c_i$ 表示第 $i$ 个点的父亲编号，以及边上的字符。
接下来一行 $n$ 个正整数 $\mathit{val}_1, \mathit{val}_2, \ldots, \mathit{val}_n$。
接下来一行 $n$ 个非负整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出一行 $n$ 个整数 $\mathit{ans}_1, \mathit{ans}_2, \ldots, \mathit{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

提示

【样例 #1 解释】

以下表格表示当 $u, i$ 固定时，式子中 $\mathit{val}_v$ 的最大值。

	$u = 1$	$u = 2$	$u = 3$	$u = 4$	$u = 5$
$i = 0$	$3$	$0$	$3$	$0$	$0$
$i = 1$	-	$4$		$4$
$i = 2$		-			$5$

---

【样例 #2】

见附件中 tree/tree2.in 与 tree/tree2.ans。

这个样例满足测试点 $3 \sim 5$ 的条件限制。

---

【样例 #3】

见附件中 tree/tree3.in 与 tree/tree3.ans。

这个样例满足测试点 $9 \sim 10$ 的条件限制。

---

【样例 #4】

见附件中 tree/tree4.in 与 tree/tree4.ans。

这个样例满足测试点 $11 \sim 12$ 的条件限制。

---

【数据范围】

对于所有数据保证 $1 \le T \le 5$，$1 \le n \le 5 \times {10}^5$，$1 \le \mathit{val}_i \le {10}^9$，$1 \le \mathit{fa}_i < i$，$c_i = \{0, 1\}$，$0 \le a_i \le n$。

具体如下：

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

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