P11162 [BalkanOI 2023] Car Race

**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day1 T1「[Car Race](https://boi2023.zotks.si/wp-content/uploads/day_1/d1_car_race/en_EN.pdf)」** 为了吸引更多的游客和资金到曾经骄傲但现在几乎被废弃的马里博尔工业区，这座城市在前 Metalna 工厂的地点建了一条赛道（Metalna 工厂是 1990 年代初被迫关闭的多家马里博尔大型企业之一）。赛道的形状是一棵有 $n$ 个顶点的有根树。树的顶点用整数 $0,1, \ldots, n-1$ 编号，根的编号是 $0$。 比赛开始了！最初，有些顶点上有赛车。每秒，每辆赛车都向着根的方向移动到相邻的顶点。在任何时刻，如果两辆或更多的赛车同时在一个编号大于 $0$ 的顶点上，它们就会相撞，不能再参加比赛。根上可以在任何时刻容纳任意数量的赛车。 对于每个顶点 $v$，输出一个整数 $c_{v}$，它的定义如下： - 如果在比赛开始时顶点 $v$ 上没有赛车，$c_{v}$ 是 $-1$。 - 否则，如果从顶点 $v$ 出发的赛车在到达根的途中相撞，那么 $c_{v}$ 是 $-1$。 - 否则，$c_{v}$ 是从顶点 $v$ 出发的赛车到达根的时间。

第一行包含一个整数 $n$，表示树的顶点数。 第二行包含 $n-1$ 个整数 $p_{1}, p_{2}, \ldots, p_{n-1}$。$p_{i}\ (1\leq i\leq n-1)$ 表示顶点 $i$ 的父亲，满足 $0 \leq p_{i}

输出一行包含 $n$ 个整数 $c_{0}, c_{1}, \ldots, c_{n-1}$，整数之间用一个空格分隔。

### 样例解释 顶点 $0$（根）在比赛开始时没有赛车。从顶点 $1$ 出发的赛车到达根需要 $1$ 秒，从顶点 $4$ 出发的赛车需要 $3$ 秒。从顶点 2 和 $3$ 出发的赛车在到达根的途中在顶点 $1$ 相撞。 ### 数据范围 对于所有输入数据，满足： - $1 \leq n \leq 10^{6}$ 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $n \leq 3$ | $3$ | | $2$ | $p_{i}=i-1\ (1\leq i\leq n-1)$ | $5$ | | $3$ | $n \leq 500$ | $8$ | | $4$ | $n \leq 3000$ | $9$ | | $5$ | $n \leq 10^{5}$ | $10$ | | $6$ | $p_{i}=\frac{i-1}{2}$ | $9$ | | $7$ | $n \leq 2 \cdot 10^{5}$ | $14$ | | $8$ | 每个顶点最多有 $3$ 个相邻的点 | $19$ | | $9$ | 无附加限制 | $23$ |