F. Token Re-Moving
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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$$$.

Example
Input
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
Output
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
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$$$.