F. Повторное перемещение фишек
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Taylor Swift - Patient Zero

Вам дано дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Изначально в вершине $$$i$$$ находится $$$a_i$$$ фишек.

Пусть дерево подвешено за некоторую вершину $$$r$$$. Операция над вершиной $$$u$$$ перемещает все фишки, находящиеся в данный момент в поддереве$$$^{\text{∗}}$$$ вершины $$$u$$$, в вершину $$$u$$$. Стоимость этой операции равна количеству фишек в вершине $$$u$$$ после перемещения.

Также вам дана перестановка $$$p_1, p_2, \ldots, p_n$$$ целых чисел от $$$1$$$ до $$$n$$$. Вес перестановки $$$p$$$ — это суммарная стоимость выполнения операций над вершинами $$$p_1, p_2, \ldots, p_n$$$ в указанном порядке.

Для каждого $$$r$$$ от $$$1$$$ до $$$n$$$ найдите вес перестановки $$$p$$$, когда дерево подвешено за вершину $$$r$$$. Для каждого $$$r$$$ операции выполняются независимо, начиная с исходного расположения фишек. Поскольку ответы могут быть большими, выведите их по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Поддеревом вершины $$$u$$$ называется подграф, состоящий из вершины $$$u$$$, всех ее потомков, и всех ребер между ними.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — количество вершин в дереве.

Каждая из следующих $$$n - 1$$$ строк содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что данные рёбра образуют дерево.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 998\,244\,353$$$), где $$$a_i$$$ — исходное количество фишек в вершине $$$i$$$.

Следующая строка содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны) — перестановку $$$p$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел, где $$$r$$$-е число — вес перестановки $$$p$$$, когда дерево подвешено за вершину $$$r$$$, по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных рассмотрим $$$r = 1$$$. Изначально количества фишек равны $$$[1]$$$. Операция над вершиной $$$p_1 = 1$$$ перемещает фишки из поддерева $$$\{1\}$$$ в вершину $$$1$$$, поэтому её стоимость равна $$$1$$$. Таким образом, вес перестановки $$$p$$$ равен $$$1$$$.

Во втором наборе входных данных рассмотрим $$$r = 1$$$. Изначально количества фишек равны $$$[5, 13]$$$.

  • Операция над вершиной $$$p_1 = 2$$$ перемещает фишки из поддерева $$$\{2\}$$$ в вершину $$$2$$$, поэтому её стоимость равна $$$13$$$. Количества фишек остаются равны $$$[5, 13]$$$.
  • Операция над вершиной $$$p_2 = 1$$$ перемещает фишки из поддерева $$$\{1, 2\}$$$ в вершину $$$1$$$, поэтому её стоимость равна $$$18$$$. Количества фишек становятся равны $$$[18, 0]$$$.
Таким образом, вес перестановки $$$p$$$ равен $$$13 + 18 = 31$$$.

В третьем наборе входных данных рассмотрим $$$r = 1$$$. Изначально количества фишек равны $$$[7, 2, 9]$$$.

  • Операция над вершиной $$$p_1 = 2$$$ перемещает фишки из поддерева $$$\{2\}$$$ в вершину $$$2$$$, поэтому её стоимость равна $$$2$$$. Количества фишек остаются равны $$$[7, 2, 9]$$$.
  • Операция над вершиной $$$p_2 = 3$$$ перемещает фишки из поддерева $$$\{3\}$$$ в вершину $$$3$$$, поэтому её стоимость равна $$$9$$$. Количества фишек остаются равны $$$[7, 2, 9]$$$.
  • Операция над вершиной $$$p_3 = 1$$$ перемещает фишки из поддерева $$$\{1, 2, 3\}$$$ в вершину $$$1$$$, поэтому её стоимость равна $$$18$$$. Количества фишек становятся равны $$$[18, 0, 0]$$$.
Таким образом, вес перестановки $$$p$$$ равен $$$2 + 9 + 18 = 29$$$.