| AIM Tech Round 3 (Div. 1) |
|---|
| Закончено |
Деревом называется связный неориентированный граф без циклов. Вам дано дерево, состоящее из n вершин, тогда центроидом дерева называется любая вершина, такая что при её удалении размер любой компоненты связности не будет превосходить 
.
Вам дано дерево размера n и разрешается выполнить не более одной операции перестановки ребра. Перестановкой ребра называется удаление одного ребра из дерева (без удаления инцидентных вершин) и добавление одного нового ребра (без добавления новых вершин) таким образом, что граф остаётся деревом. Требуется для каждой вершины дерева определить, правда ли, что её можно сделать центроидом, выполнив не более одной перестановки ребра.
В первой строке входных данных записано целое число n (2 ≤ n ≤ 400 000) — количество вершин в дереве. Каждая из последующих n - 1 строк содержит пару номеров вершин ui и vi (1 ≤ ui, vi ≤ n), являющихся концами одного из рёбер дерева.
Выведите n чисел, i-е из которых равно 1, если i-ю вершину можно сделать центроидом, выполнив не более одной перестановки ребра, и 0 в противном случае.
3
1 2
2 3
1 1 1
5
1 2
1 3
1 4
1 5
1 0 0 0 0
В первом тестовом примере любую вершину можно сделать центроидом. Например, чтобы сделать центроидом вершину 1, нужно заменить ребро (2, 3) на ребро (1, 3).
