CF2277F Token Re-Moving

[Taylor Swift - Patient Zero](https://open.spotify.com/track/11hcBLPtbMp4aQI6zGQLub) 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.

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

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

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