Алиса и Боб собираются отмечать Рождество, играя в игру с деревом подарков. Дерево состоит из $$$n$$$ вершин (пронумерованных от $$$1$$$ до $$$n$$$, вершина $$$r$$$ является корнем). На $$$i$$$-й вершине висят $$$a_i$$$ подарков.
Перед началом игры выбирается некоторое целое число $$$k$$$. Затем игра проходит следующим образом:
Для каждого возможного корня дерева сообщите, кто выиграет игру — Алиса или Боб.
Глубина вершины $$$i$$$ в дереве с корнем $$$r$$$ определяется, как количество ребер на простом пути из вершины $$$r$$$ до вершины $$$i$$$. Глубина корня $$$r$$$ равна нулю.
В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ $$$(3 \le n \le 10^5, 1 \le k \le 20)$$$.
В каждой из следующих $$$n-1$$$ строк записаны два целых числа $$$x$$$ и $$$y$$$ $$$(1 \le x, y \le n, x \neq y)$$$, описывающие неориентированное ребро между двумя вершинами $$$x$$$ и $$$y$$$. Эти ребра образуют дерево из $$$n$$$ вершин.
В следующей строке записаны $$$n$$$ целых чисел, задающих массив $$$a$$$ $$$(0 \le a_i \le 10^9)$$$.
Выведите $$$n$$$ целых чисел, где $$$i$$$-е число равно $$$1$$$, если Алиса выиграет игру, если дерево подвешено за вершину $$$i$$$, и $$$0$$$ в противном случае.
5 1 1 2 1 3 5 2 4 3 0 3 2 4 4
1 0 0 1 1
Посчитаем ответ для примера с корнем в 1 и в 2.
Корень 1
Алиса всегда выигрывает в данном случае. Возможная игра между Алисой и Бобом выглядит так:
Боб не может сделать ход, а потому проигрывает.
Корень 2
Боб всегда выигрывает в данном случае. Пример игры:
Алиса не может сделать ход, а потому проигрывает.
Название |
---|