题意
给定一张 \(n\) 个点的有向图，每个点都有一条出边。
初始保证所有点都能走到 \(1\)。
你需要重新规划最少的出边，使得最终每个节点都存在一条长度为 \(k\) 的路径走到节点 \(1\)。
\(n \le 10 ^ 6\)
Sol
显然给定的图为一棵基环树。
对环与树分类讨论。
首先注意到每个点都能走到 \(1\)，说明 \(1\) 一定在环上。
注意到若想使得环上所有点都满足条件，一个一定不劣的操作是将 \(1\) 连成自环。
可以考虑若 \(1\) 不为自环，且 \(k \ge 2\)，则在环上距离 \(1\) 不超过 \(k\) 的节点是无法走 \(k\) 的路径到达 \(1\) 的。
将 \(1\) 的出边断开，题目变成在一棵树上选择若干节点连到根，使得深度不超过 \(k\)。
考虑从下至上的贪心，容易发现，若当前有一节点 \(u\)，使得 \(v \in subtree(u)\)，\(dis(u, v) = k\) 时，选择当前的 \(u\) 一定最优因为显然选择 \(son_u\) 不会比选择 \(u\) 更优。
ro
标签：AGC004D,Teleporter,环上,自环,出边,节点 From： https://www.cnblogs.com/cxqghzj/p/18395496