Problem Description

You are given a rooted tree with $n$ nodes, with node $1$ as the root. Each edge has a character $c \in \{0, 1\}$. Let $S_u$ be the string formed by writing down, in order, the characters on the path from the root to node $u$. It is guaranteed that, for each node, the characters on the edges from this node to its children are pairwise distinct.

For each node $u$, there is a value $\mathit{val}_u$ and a limit $a_u$. For a node $u$, if a node $v$ satisfies that $S_u$ is a suffix of $S_v$, then we call $v$ an extension node of $u$.

Alice has a string $S$. Initially, let $S = S_u$. Now she can delete some suffix characters so that $S$ becomes $S'$, and then tell $S'$ to Bob.

Bob receives a string $S'$. He needs to append some characters after $S'$ to obtain $S''$. For an extension node $v$ of some $u$, if $S'' = S_v$ and $\lvert S' \rvert \ge a_v$, then Bob gains profit $\mathit{val}_v$. Of course, Bob can perform such an operation only once, so he will choose, among all valid $v$, the one with the maximum $\mathit{val}_v$. If there is no valid $v$, Bob can gain only $0$.

Now Alice wants to know: among all $\lvert S \rvert + 1$ deletion choices (deleting $0 \sim \lvert S \rvert$ characters), what is the sum of the profits Bob can obtain?

For each $u$, you need to answer Alice’s query.

Formally:

For each node $u$, compute $\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$。

In particular, if for some $u$ there is no $v$ satisfying the conditions, then $\max = 0$.

Here $S[l, r]$ denotes the substring consisting of the $l$-th to the $r$-th characters of string $S$. In particular, $S[x + 1, x]$ denotes the empty string. $\lvert S \rvert$ denotes the length of $S$, and $\land$ means “and”.

Input Format

Multiple test cases. The first line contains an integer $T$, denoting the number of test cases.
For each test case, the first line contains a positive integer $n$, denoting the number of nodes.
The next $n - 1$ lines each contain two integers $\mathit{fa}_i, c_i$, denoting the parent index of node $i$ and the character on the edge.
The next line contains $n$ positive integers $\mathit{val}_1, \mathit{val}_2, \ldots, \mathit{val}_n$.
The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$.

Output Format

Output one line with $n$ integers $\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

Hint

[Sample #1 Explanation]

The following table shows, for fixed $u$ and $i$, the maximum value of $\mathit{val}_v$ in the formula.

[Sample #2]

See the attachments tree/tree2.in and tree/tree2.ans.

This sample satisfies the constraints of test points $3 \sim 5$.

[Sample #3]

See the attachments tree/tree3.in and tree/tree3.ans.

This sample satisfies the constraints of test points $9 \sim 10$.

[Sample #4]

See the attachments tree/tree4.in and tree/tree4.ans.

This sample satisfies the constraints of test points $11 \sim 12$.

[Constraints]

For all testdata, it is guaranteed that $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 \in \{0, 1\}$, and $0 \le a_i \le n$.

Specifically:

Special property A: $c_i = 0$.
Special property B: $\mathit{fa}_i = \lfloor \frac{i}{2} \rfloor$.

Translated by ChatGPT 5