题解

思路推导

把输入中的第 $i$ 条边赋予编号 $i$。设顶点 $v$ 的父边编号为 $id_v$。当父顶点在某一轮通过编号 $id_u$ 的边被画出后，如果子边编号大于 $id_u$，本轮稍后仍会扫描到这条边，子顶点可以在同一轮画出；否则只能等下一轮。

因此，沿根到任意顶点的路径，每出现一次边编号下降，所需轮次就增加一次。

做法

以顶点 $1$ 为根遍历树。根的轮次设为 $1$，父边编号设为 $0$。从 $u$ 走到子顶点 $v$ 时，若边编号小于父边编号，则令 $v$ 的轮次为 $u$ 的轮次加一；否则轮次不变。

所有顶点轮次的最大值就是最后一个顶点被画出的轮次，也就是读边次数。

正确性证明

对根到顶点的距离归纳。根在第 $0$ 步已经画出，并从第 $1$ 轮开始传播。假设父顶点 $u$ 的记录轮次和父边编号正确。若子边编号更大，则在画出 $u$ 的同一轮中，扫描位置尚未越过子边，故 $v$ 在同轮画出；若子边编号更小，本轮已错过该边，下一次扫描时它一定会被处理，故恰晚一轮。

转移与实际扫描完全一致，所以每个顶点的轮次均正确。算法结束所需轮次是所有顶点画出轮次的最大值，因而输出正确。

复杂度分析

树的每条边被访问常数次，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。