← 返回题目列表

Codeforces · 1009/F

F. 主导指数

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的有根无向树。顶点 $$$1$$$ 是根。

让我们将顶点 $$$x$$$ 的深度数组表示为无限序列 $$$[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$$$,其中 $$$d_{x, i}$$$ 是顶点数 $$$y$$$ ,使得两个条件都成立:

- $$$x$$$ 是 $$$y$$$ 的祖先;
- 从 $$$x$$$ 到 $$$y$$$ 的简单路径恰好遍历 $$$i$$$ 边。

顶点 $$$x$$$ 的深度数组的主导索引(或者简单地说,顶点 $$$x$$$ 的主导索引)是一个索引 $$$j$$$,使得:

- 对于每个 $$$k < j$$$,$$$d_{x, k} < d_{x, j}$$$;
- 对于每个 $$$k > j$$$,$$$d_{x, k} \le d_{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$$$ 的主导索引。

示例

输入 #1

4
1 2
2 3
3 4

输出 #1

0
0
0
0

输入 #2

4
1 2
1 3
1 4

输出 #2

1
0
0
0

输入 #3

4
1 2
2 3
2 4

输出 #3

2
1
0
0