[图论记录]AT2044 [AGC004D] Teleporter

**题意** ： 给出一个 $n$ 个点的有向图，每个点都有恰好一条出边。 保证每个点都能到达 $1$ 号点，现在要修改一些出边的目的地，使得从任意点出发走 $k$ 步都恰好到达 $k$。 问至少需要修改多少次出边。 $n\leq 10^5$ ，时限 $\texttt{1s}$。 ------------ 原图为一棵基环内向树。 首先不难发现需要将 $1$ 号点的出边改为自环。 由于每个点都能到达 $1$ 号点，所以 $1$ 必然在环上。 于是图会变为一棵内向树，目标是让所有点到根的距离都不超过 $k$。 设 $d[u]$ 为 $u$ 到子树内点的最大距离。 每次将 $d[u]=k-1$ 的所有点与 $1$ 直接相连，不断重复此过程，则可得到最优解。 可以用一次 $\rm dfs$ 以 $O(n)$ 的复杂度完成，具体见代码。 ```cpp #include<algorithm> #include<cstdio> #include<vector> #define MaxN 100500 using namespace std; vector<int> g[MaxN]; int n,k,ans,d[MaxN]; void dfs(int u,int fa) { for (int i=0;i<g[u].size();i++){ dfs(g[u][i],u); d[u]=max(d[u],d[g[u][i]]); }d[u]++; if (d[u]==k&&fa>1){ans++;d[u]=0;} } int main() { scanf("%d%d",&n,&k); for (int i=1,fa;i<=n;i++){ scanf("%d",&fa); if (i==1)ans+=(fa!=1); else g[fa].push_back(i); }dfs(1,0); printf("%d",ans); return 0; } ```