markdown

F. 支配指标

时间限制：每个测试点 $4.5$ 秒
内存限制：每个测试点 $512$ MB
输入：标准输入
输出：标准输出

题目描述

给定一棵有根无向树，包含 $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$，满足：

• 对于所有 $i < j$，有 $d_{x,i} < d_{x,j}$；
• 对于所有 $i > j$，有 $d_{x,i} \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