E. Кирей атакует поместье
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Кирей подло пробрался в полное ловушек поместье Айнцбернов, но был обнаружен фамильяром Кирицугу. Оценив свои силы, Кирей решил отступить. Поместье представляет собой дерево из $$$n$$$ вершин с корнем в вершине $$$1$$$. В каждой вершине дерева записано число $$$a_i$$$ — опасность вершины $$$i$$$. Напомним, что деревом называется связный неориентированный граф без циклов.

Чтобы отступление оказалось успешным, Кирей должен вычислить для каждой вершины значение угрозы. Угроза вершины равна максимальной знакопеременной сумме на вертикальном пути с началом в этой вершине. Знакопеременная сумма на вертикальном пути с началом в вершине $$$i$$$ равна $$$a_i - a_{p_i} + a_{p_{p_i}} - \ldots$$$, где $$$p_i$$$ — родитель вершины $$$i$$$ на пути к корню (к вершине $$$1$$$).

Например, в дереве ниже у вершины $$$4$$$ есть следующие вертикальные пути:

  • $$$[4]$$$ с знакопеременной суммой $$$a_4 = 6$$$;
  • $$$[4, 3]$$$ с знакопеременной суммой $$$a_4 - a_3 = 6 - 2 = 4$$$;
  • $$$[4, 3, 2]$$$ с знакопеременной суммой $$$a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$$$;
  • $$$[4, 3, 2, 1]$$$ с знакопеременной суммой $$$a_4 - a_3 + a_2 - a_1 = 6 - 2 + 5 - 4 = 5$$$.
Красным цветом указаны опасности вершин.

Помогите Кирею вычислить значения угроз для всех вершин и покинуть поместье.

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

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

Далее следует описание наборов.

В первой строке дано целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — опасности вершин.

В следующих $$$n - 1$$$ строках даны числа $$$v, u$$$ ($$$1 \le v, u \le n$$$, $$$v \neq u$$$) — описание рёбер дерева.

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

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел — угрозу каждой вершины.

Пример
Входные данные
2
5
4 5 2 6 7
1 2
3 2
4 3
5 1
6
1000000000 500500500 900900900 9 404 800800800
3 4
5 1
2 5
1 6
6 4
Выходные данные
4 5 2 9 7 
1000000000 1500500096 1701701691 199199209 404 800800800
Примечание

Дерево из первого набора входных данных изображено в условии, максимальные знакопеременные суммы достигаются следующим образом:

  1. $$$a_1 = 4$$$;
  2. $$$a_2 = 5$$$;
  3. $$$a_3 = 2$$$;
  4. $$$a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$$$;
  5. $$$a_5 = 7$$$.