Задано корневое неориентированное дерево, состоящее из $$$n$$$ вершин. Вершина $$$1$$$ является корнем.
Определим массив глубин вершины $$$x$$$, как бесконечную последовательность $$$[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$$$, где $$$d_{x, i}$$$ — это количество вершин $$$y$$$ таких, что выполняются оба следующих условия:
Доминирующий индекс массива глубин вершины $$$x$$$ (или же просто доминирующий индекс вершины $$$x$$$) — это такой индекс $$$j$$$, что:
Для каждой вершины дерева вычислите ее доминирующий индекс.
В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество вершин в дереве.
Затем следует $$$n - 1$$$ строка, в каждой записаны по два целых числа $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$, $$$x \ne y$$$). Эта строка задает ребро в дереве.
Гарантируется, что данные ребра образуют дерево.
Выведите $$$n$$$ чисел. $$$i$$$-е число должно быть равно доминирующему индексу вершины $$$i$$$.
4
1 2
2 3
3 4
0
0
0
0
4
1 2
1 3
1 4
1
0
0
0
4
1 2
2 3
2 4
2
1
0
0
Название |
---|