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

Дано дерево с $$$n$$$ вершинами, пронумерованными от $$$1$$$ до $$$n$$$. В вершине $$$i$$$ записано целое число $$$a_{i}$$$ для каждого $$$i = 1, 2, \ldots, n$$$. Ваша цель — сделать все $$$a_{i}$$$ одинаковыми, выполнив несколько заклинаний (возможно, ни одного).

Предположим, что корнем дерева выбрана некоторая вершина. Чтобы выполнить заклинание, можно выбрать произвольную вершину $$$v$$$ и произвольное неотрицательное целое число $$$c$$$. Затем для каждой вершины $$$i$$$ в поддереве$$$^{\dagger}$$$ $$$v$$$ нужно заменить $$$a_{i}$$$ на $$$a_{i} \oplus c$$$. Стоимость такого заклинания равна $$$s \cdot c$$$, где $$$s$$$ — число вершин в поддереве. Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Пусть $$$m_r$$$ — минимально возможная суммарная стоимость, за которую можно сделать все $$$a_i$$$ равными, в случае если вершина $$$r$$$ выбрана корнем дерева. Найдите $$$m_{1}, m_{2}, \ldots, m_{n}$$$.

$$$^{\dagger}$$$ Пусть вершина $$$r$$$ выбрана корнем дерева. Тогда вершина $$$i$$$ принадлежит поддереву $$$v$$$, если простой путь от $$$i$$$ до $$$r$$$ содержит $$$v$$$.

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

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

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

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

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

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

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

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

Для каждого набора входных данных выведите $$$m_1, m_2, \ldots, m_n$$$ на отдельной строке.

Пример
Входные данные
2
4
3 2 1 0
1 2
2 3
2 4
1
100
Выходные данные
8 6 12 10 
0
Примечание

В первом наборе входных данных, чтобы найти $$$m_1$$$, подвесим дерево за вершину $$$1$$$.

  1. На первом заклинании выберем $$$v=2$$$ и $$$c=1$$$. После выполнения этого заклинания $$$a$$$ станет равным $$$[3, 3, 0, 1]$$$. Стоимость этого заклинания равна $$$3$$$.
  2. На втором заклинании выберем $$$v=3$$$ и $$$c=3$$$. После выполнения этого заклинания $$$a$$$ станет равным $$$[3, 3, 3, 1]$$$. Стоимость этого заклинания равна $$$3$$$.
  3. На третьем заклинании выберем $$$v=4$$$ и $$$c=2$$$. После выполнения этого заклинания $$$a$$$ станет равным $$$[3, 3, 3, 3]$$$. Стоимость этого заклинания равна $$$2$$$.

Теперь все значения в массиве $$$a$$$ одинаковы, а суммарная стоимость равна $$$3 + 3 + 2 = 8$$$.

Значения $$$m_2$$$, $$$m_3$$$, $$$m_4$$$ находятся аналогично.

Во втором наборе входных данных цель уже достигнута, поскольку в дереве всего одна вершина.