题解

本题描述了 $n$ 个蜘蛛在功能图上的传递过程，需要求出第一次达到稳定的年份。下面对题目进行详细分析，并给出与标程对应的算法步骤。

1. 图的模型与性质

蜘蛛之间的传递关系构成一张 功能图（每个结点有且仅有一条出边）。这样的图由若干个连通分量组成，每个分量恰好包含一个环，其余结点形成指向环的树。

记 $r_i$ 为蜘蛛 $i$ 传递的目标。由于 $r_i \neq i$，图中不存在自环。

初始时所有蜘蛛都有一个毛绒玩具，每年同时进行传递：若蜘蛛有玩具，则给 $r_i$ 一个，自己不再保留该玩具；然后，若某蜘蛛收到的玩具数超过 $1$，则丢掉多余部分，只保留 $1$ 个。简单版中这个“截断”规则非常关键。

2. 稳定年份的分析

定义 第 $k$ 年交换前 的状态为 $A_k$。$A_1$ 全为 $1$。第 $1$ 年交换后得到 $A_2$，依此类推。若存在 $y > 1$ 使得 $A_y = A_{y-1}$，则第 $y$ 年为第一次稳定年份。

观察：

• 环上的结点相互传递，每个环上结点每年都会收到至少一个玩具，因此它们永远有 $1$ 个玩具。
• 不在环上的结点，其玩具会沿着出边向环移动，最终全部进入环中，而自身玩具数变为 $0$。
• 一旦所有树上的玩具都进入环，且环上每个结点恰有 $1$ 个玩具，状态就不再改变。

设某个树结点 $u$ 到环的距离为 $dist(u)$（沿有向边走到环的步数）。初始时 $u$ 拥有的玩具需要经过 $dist(u)$ 次传递才能到达环，同时 $u$ 本身在第一次传递后就变为 $0$。因此，树上的所有玩具都进入环所需的年数，就是所有树结点到环距离的最大值，记为 $D$。

经过 $D$ 次传递后（即 $A_{D+1}$），树上所有结点玩具数均为 $0$，环上均为 $1$。此时再经过一次传递（第 $D+1$ 次），状态不变，故 $A_{D+2} = A_{D+1}$。所以答案为

特别地，若整张图就是一个大环（无树枝），则 $D = 0$，答案为 $2$，与样例一致。

3. 计算最大距离 $D$

由于每个点出度为 $1$，找环并计算树上结点深度的常用方法是：

1. 先找出所有环上的结点（可利用拓扑排序删去所有入度为 $0$ 的结点）。
2. 从环上结点出发，沿反图（入边）做 BFS/DFS，得到每个树上结点的深度。

标程使用了更简洁的 按层剥叶子 的方法，在拓扑排序的同时直接统计层数，该层数就是 $D$。算法过程如下：

• 计算每个结点的入度 $d[i]$。
• 将所有结点按入度放入有序集合 set。
• 初始化 $ans = 2$。
• 不断执行下列操作，直到不存在入度为 $0$ 的结点：
  1. 取出当前所有入度为 $0$ 的结点（它们位于同一层）。
  2. 对每个这样的结点 $k$：
     • 将其从集合中删除；
     • 将其后继 $r_k$ 的入度 $d[r_k]$ 减 $1$；
     • 若后继在集合中存在，则删除旧记录，并暂存到队列中，等待重新插入。
  3. 将该层处理完毕后，将队列中所有入度更新过的结点重新插入集合。
  4. 令 $ans$ 增加 $1$。

循环结束时，集合中只剩下环上的结点（入度均 $\ge 1$）。期间 $ans$ 从 $2$ 开始，每剥离一层叶子就加 $1$，因此 $ans$ 最终等于 $D + 2$。

正确性解释：每一轮同时删除的入度为 $0$ 的结点，恰好是当前所有距离环最远的叶子结点，剥离的轮数就是最大距离 $D$。例如链 $5\to3\to4\to2$（环为 $1$-$2$），第一轮删 $5$，第二轮删 $3$，第三轮删 $4$，共 $3$ 轮，对应 $D=3$，答案 $5$。

4. 时间复杂度

每个结点最多从集合中删除和插入一次，set 操作每次 $O(\log n)$，总复杂度 $O(n \log n)$。由于所有测试数据的 $n$ 总和不超过 $2\cdot 10^5$，可轻松通过。

5. 总结

本题的关键在于发现过程稳定当且仅当所有玩具都汇集于环上，而所需年数等于树上结点到环的最大距离 $+2$。标程通过模拟“逐层删除入度为 $0$ 的结点”同时统计层数，巧妙且高效地得到了答案。