AGC004D Teleporter

题意 ： 给出一个 个点的有向图，每个点都有恰好一条出边。

保证每个点都能到达 号点，现在要修改一些出边的目的地，使得从任意点出发走 步都恰好到达 。

问至少需要修改多少次出边。

，时限 。

---

原图为一棵基环内向树。

首先不难发现需要将 号点的出边改为自环。

由于每个点都能到达 号点，所以 必然在环上。

于是图会变为一棵内向树，目标是让所有点到根的距离都不超过 。

设 为 到子树内点的最大距离。

每次将 的所有点与 直接相连，不断重复此过程，则可得到最优解。

可以用一次 以 的复杂度完成。