CF1009F Dominant Indices

给定一棵有 $n$ 个顶点的有根树，以顶点 $1$ 作为根。 我们定义顶点 $x$ 的深度数组为一个无限序列 $[d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots]$，其中 $d_{x, i}$ 表示满足以下两个条件的顶点 $y$ 的数量： - $x$ 是 $y$ 的祖先； - 从 $x$ 到 $y$ 的简单路径恰好经过 $i$ 条边。 顶点 $x$ 的深度数组的主导下标（dominant index）（简称顶点 $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$ 的主导下标。

由 ChatGPT 4.1 翻译