G2. 中等恶魔问题（困难版）题解

本题是 G1 的升级版，核心区别在于不再限制每只蜘蛛的玩具数量上限，因此树上的玩具会持续向环汇聚并累积在环上，直到所有玩具都进入环中且数量不再变化为止。

1. 图的模型与问题转化

与 G1 相同，$n$ 个蜘蛛的传递关系构成一张功能图（每个结点出度为 $1$），由若干连通分量组成，每个分量恰好包含一个环，其余结点形成指向环的有向树。

关键观察：一旦所有玩具都进入环中，且每个蜘蛛每年传递的数量固定，则整个系统的玩具分布将进入稳定状态。困难版中玩具可以累加，因此稳定条件变为：所有不在环上的结点玩具数均为 $0$，环上结点的玩具数不再改变。

2. 玩具流失时间的计算

对于任意不在环上的结点 $i$，设它到环的路径上的结点集合为 $T(i)$（包含 $i$ 本身）。初始时 $i$ 有 $1$ 个玩具，每年这个玩具会沿着路径向环移动一步。同时，$i$ 的后代结点（以 $i$ 为根的子树中的结点）的玩具也会陆续经过 $i$。

因此，结点 $i$ 的玩具总数（包括自身初始的 $1$ 个）等于其子树大小（以环方向为根的树，边方向反转）。记 $v[i]$ 为以 $i$ 为根的子树中初始玩具的总数，也就是子树中的结点个数。结点 $i$ 需要 $v[i]$ 年才能将所有玩具传递给父结点（或环），自身玩具数在第 $v[i]$ 年后变为 $0$。

对于环上的结点，它们始终有玩具流入，且自身初始也有玩具，因此永远不会变为 $0$。

3. 稳定年份的推导

设所有不在环上的结点的最大 $v[i]$ 值为 $M$，即最深的树需要 $M$ 年才能将全部玩具送入环中。经过 $M$ 次传递后，所有树结点玩具数为 $0$，环上玩具分布固定。再经过一次传递（第 $M+1$ 次），状态与第 $M$ 次相同，因此第一次稳定年份为：

这与 G1 的结论形式相同，但 $M$ 的定义从“到环的距离”变为“子树大小”。

4. 算法实现

标程通过拓扑排序（剥叶子）从下往上计算每个结点的子树大小，同时维护全局最大值。

算法步骤：

1. 计算入度：对于每个 $i$，将出边 $i \to r_i$ 视为入度关系，即 $r_i$ 的入度 $d[r_i]$ 加 $1$。
2. 初始化：所有结点初始玩具数 $v[i] = 1$，答案 $\text{ans} = 2$。
3. 拓扑排序：将所有结点按入度存入有序集合（或优先队列），每次取出所有入度为 $0$ 的结点：
   • 当前结点 $k$ 的 $v[k]$ 即为以 $k$ 为根的子树的总玩具数。
   • 更新答案：$\text{ans} = \max(\text{ans}, v[k] + 2)$。
   • 将 $v[k]$ 累加到父结点 $r_k$ 上：$v[r_k] += v[k]$。
   • 将 $r_k$ 的入度减 $1$，若变为 $0$ 则加入下一轮处理。
4. 终止条件：当集合中不再有入度为 $0$ 的结点时，剩余结点均为环上结点（入度均 $\ge 1$），它们不再贡献更新，算法结束。

正确性说明：每次处理的入度为 $0$ 的结点是当前图中的叶子（即最远离环的结点），它们在被处理时已经累积了其所有后代结点的玩具数，因此 $v[k]$ 恰好是其子树大小。答案取所有 $v[k] + 2$ 的最大值，对应需要最长时间将玩具送入环的子树。

时间复杂度：每个结点最多入队一次，集合操作 $O(\log n)$，总复杂度 $O(n \log n)$，满足 $\sum n \le 2\times 10^5$ 的限制。

5. 样例分析

以第三个测试用例 $n=5, r=[2,1,4,2,3]$ 为例：

• 环：$1 \to 2 \to 1$。
• 树：$3 \to 4 \to 2$，$5 \to 3$。
• 子树大小：$v[5]=1$，$v[3]=2$（包含 $5$），$v[4]=3$（包含 $3,5$）。
• 最大值 $M=3$，答案 $3+2=5$，与输出一致。

6. 总结

困难版的核心在于将“到环的距离”扩展为“子树大小”，因为玩具不再被丢弃而是累积传递。标程通过拓扑排序优雅地自底向上累加子树大小，并取最大值 $+2$ 得到答案，与 G1 的思路一脉相承但更深刻。