题解 AT2044 【[AGC004D] Teleporter】
ez_lcw
2020-11-03 18:37:32
先不看 $1$ 号点连出去的那条边，那么剩下来的就是一棵内向树。
对于这棵树来说，发现那些与 $1$ 号点的距离小于 $k$ 的点来说，他们肯定需要一条 $1$ 号点的自环来满足条件，否则肯定有一些点无论怎么改都到达不了 $1$ 号点。
得到了这个结论，剩下的就很好搞了，我们从下往上贪心：一旦遇到以当前点 $u$ 为根的子树的最深的未被满足的点到自己的距离等于 $k-1$，我们就可以让 $u$ 向 $1$ 连一条边，然后这棵子树的点都能被满足。
至于过程一遍 $\texttt{dfs}$ 就好了，然后也有一些细节，详见代码：
```cpp
#include<bits/stdc++.h>
#define N 100010
using namespace std;
int n,k,ans,a[N];
int cnt,head[N],nxt[N],to[N];
void adde(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int dfs(int u,int dep)
{
int maxdep=dep;//维护以点 $u$ 为根的子树的最深的未被满足的点的深度
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
maxdep=max(maxdep,dfs(v,dep+1));
}
if(maxdep-dep==k-1)//如果最深点到当前点的距离为k
{
if(a[u]!=1)//注意如果原来有了连向1的边就不用统计进ans了
{
a[u]=1;
ans++;
}
return dep-1;
}
return maxdep;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(i!=1) adde(a[i],i);
}
dfs(1,1);
if(a[1]!=1) ans++;//1号点自环
printf("%d\n",ans);
return 0;
}
/*
6 2
2 1 1 3 3 4
*/
```