Дано дерево с \(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\).
Выходные данные
Для каждого набора входных данных выведите \(m_1, m_2, \ldots, m_n\) на отдельной строке.
Примечание
В первом наборе входных данных, чтобы найти \(m_1\), подвесим дерево за вершину \(1\).
- На первом заклинании выберем \(v=2\) и \(c=1\). После выполнения этого заклинания \(a\) станет равным \([3, 3, 0, 1]\). Стоимость этого заклинания равна \(3\).
- На втором заклинании выберем \(v=3\) и \(c=3\). После выполнения этого заклинания \(a\) станет равным \([3, 3, 3, 1]\). Стоимость этого заклинания равна \(3\).
- На третьем заклинании выберем \(v=4\) и \(c=2\). После выполнения этого заклинания \(a\) станет равным \([3, 3, 3, 3]\). Стоимость этого заклинания равна \(2\).
Теперь все значения в массиве \(a\) одинаковы, а суммарная стоимость равна \(3 + 3 + 2 = 8\).
Значения \(m_2\), \(m_3\), \(m_4\) находятся аналогично.
Во втором наборе входных данных цель уже достигнута, поскольку в дереве всего одна вершина.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3 2 1 0
1 2
2 3
2 4
1
100
|
8 6 12 10
0
|