Token Re-Moving

Taylor Swift - Patient Zero

You are given a tree with $n$ vertices, numbered from $1$ to $n$. Initially, vertex $i$ contains $a_i$ tokens.

Suppose the tree is rooted at some vertex $r$. An operation on a vertex $u$ moves all tokens currently located in the subtree$^{\text{∗}}$ of $u$ to vertex $u$. The cost of this operation is the number of tokens at vertex $u$ after the move.

You are also given a permutation $p_1, p_2, \ldots, p_n$ of the integers from $1$ to $n$. The weight of $p$ is the total cost of performing the operations on vertices $p_1, p_2, \ldots, p_n$ in this order.

For each $r$ from $1$ to $n$, find the weight of $p$ when the tree is rooted at vertex $r$. For each $r$, the operations are performed independently, starting from the initial placement of tokens. Since the answers might be large, output them modulo $998\,244\,353$.

$^{\text{∗}}$A subtree of vertex $u$ is the subgraph consisting of $u$, all its descendants, and all the edges between them.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the number of vertices in the tree.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — an edge between vertices $u$ and $v$. It is guaranteed that the given edges form a tree.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 998\,244\,353$), where $a_i$ is the initial number of tokens at vertex $i$.

The next line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct) — the permutation $p$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

Output

For each test case, output $n$ integers, where the $r$-th integer is the weight of $p$ when the tree is rooted at vertex $r$, modulo $998\,244\,353$.

Note

In the first test case, consider $r = 1$. Initially, the token counts are $[1]$. The operation on vertex $p_1 = 1$ moves the tokens of the subtree $\{1\}$ to vertex $1$, so its cost is $1$. Thus, the weight of $p$ is $1$.

In the second test case, consider $r = 1$. Initially, the token counts are $[5, 13]$.

• The operation on vertex $p_1 = 2$ moves the tokens of the subtree $\{2\}$ to vertex $2$, so its cost is $13$. The token counts stay $[5, 13]$.
• The operation on vertex $p_2 = 1$ moves the tokens of the subtree $\{1, 2\}$ to vertex $1$, so its cost is $18$. The token counts become $[18, 0]$.

Thus, the weight of $p$ is $13 + 18 = 31$.

In the third test case, consider $r = 1$. Initially, the token counts are $[7, 2, 9]$.

• The operation on vertex $p_1 = 2$ moves the tokens of the subtree $\{2\}$ to vertex $2$, so its cost is $2$. The token counts stay $[7, 2, 9]$.
• The operation on vertex $p_2 = 3$ moves the tokens of the subtree $\{3\}$ to vertex $3$, so its cost is $9$. The token counts stay $[7, 2, 9]$.
• The operation on vertex $p_3 = 1$ moves the tokens of the subtree $\{1, 2, 3\}$ to vertex $1$, so its cost is $18$. The token counts become $[18, 0, 0]$.

Thus, the weight of $p$ is $2 + 9 + 18 = 29$.

6
1
1
1
2
1 2
5 13
2 1
3
1 2
1 3
7 2 9
2 3 1
4
1 2
1 3
2 4
3 1 4 1
3 2 4 1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
17 23 31 12 8 45 19 62
4 3 6 1 7 8 2 5
10
1 2
1 3
2 4
2 5
3 6
3 7
4 8
5 9
6 10
101 203 157 59 311 83 97 127 41 67
3 10 2 8 1 7 5 6 9 4

1
31 18
29 18 20
15 13 9 21
540 557 363 217 426 300 436 591
2391 1650 1246 2837 2544 2409 2395 2710 3749 2342