D. Значение дерева
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для дерева $$$T$$$ с корнем $$$r$$$, где каждой вершине $$$u$$$ соответствует значение $$$a_u$$$, определим его стоимость следующим образом:

$$$$$$\sum_{u\in T} (a_u \cdot d(r,u))$$$$$$

Здесь сумма берётся по всем вершинам $$$u$$$ в дереве $$$T$$$, а $$$d(r,u)$$$ обозначает количество рёбер на кратчайшем пути от вершины $$$r$$$ до вершины $$$u$$$ в дереве.

Вам дано дерево, состоящее из $$$n$$$ вершин, с корнем в вершине $$$1$$$. Каждой вершине $$$i$$$ соответствует значение $$$a_i$$$. Для каждого $$$r$$$ от $$$1$$$ до $$$n$$$ решите следующую задачу независимо:

Рассмотрите поддерево вершины $$$r$$$ относительно вершины $$$1$$$. Формально, поддерево вершины $$$r$$$ — это дерево, состоящее из всех вершин $$$u$$$, таких что кратчайший путь от $$$1$$$ до $$$u$$$ проходит через $$$r$$$.

Найдите максимальную стоимость поддерева после выполнения не более одной операции следующего типа на поддереве:

  • Выберите любую вершину $$$u$$$ ($$$u \neq r$$$). Удалите ребро от $$$u$$$ к родителю вершины $$$u$$$$$$^{\text{∗}}$$$. Затем добавьте ребро от $$$u$$$ к любой вершине $$$v$$$, которая всё ещё достижима от $$$r$$$. Можно показать, что после этой операции граф останется деревом.
В качестве примера ниже показан пример операции с $$$r=1$$$, $$$u=5$$$ и $$$v=4$$$.

$$$^{\text{∗}}$$$Формально, удалите ребро от $$$u$$$ к $$$p$$$, где $$$p$$$ — единственная вершина, удовлетворяющая $$$d(u,p)=1$$$ и $$$d(u,r)=d(p,r)+1$$$

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

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

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$).

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

Гарантируется, что заданные рёбра образуют дерево.

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

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

Для каждого набора входных данных выведите $$$n$$$ чисел — ответы для $$$r=1,2,\ldots,n$$$.

Пример
Входные данные
3
5
1 3 2 1 2
1 2
2 3
3 4
3 5
7
1 2 3 1 3 2 1
1 2
2 3
3 4
4 5
4 6
3 7
5
5 4 3 2 1
1 2
2 3
3 4
4 5
Выходные данные
18 10 5 0 0 
40 28 18 8 0 0 0 
20 10 4 1 0
Примечание

В первом наборе входных данных, для $$$r=1$$$, оптимально выбрать $$$u=5$$$ и $$$v=4$$$. Стоимость дерева тогда равна $$$1\cdot 0 + 3\cdot 1+2\cdot 2+1\cdot 3+2\cdot 4=18$$$. Можно показать, что большую стоимость получить нельзя.

Для $$$r=4$$$, например, в поддереве только $$$1$$$ вершина, поэтому операция невозможна. Единственная возможная стоимость поддерева — $$$0$$$.