CodeForces - 1065F(树形dp)
90nwyn
2020-12-02 15:40:41
[题目链接](https://vjudge.net/problem/CodeForces-1065F)
------------
------------
```cpp
#include <bits/stdc++.h>
using namespace std;
const int M=1e6+5;
int n,k,dep[M],low[M],dp[M],ans[M];
vector<int> vt[M];
void dfs(int x)
{
if(vt[x].empty())return low[x]=dep[x],ans[x]=dp[x]=1,void();
low[x]=M;
for(auto y:vt[x])
{
dep[y]=dep[x]+1;
dfs(y);
if(low[y]-dep[x]<=k)
low[x]=min(low[x],low[y]),dp[x]+=dp[y];
}
ans[x]=dp[x];
for(auto y:vt[x])
ans[x]=max(ans[x],dp[x]+ans[y]-(low[y]-dep[x]<=k?dp[y]:0));
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=2;i<=n;i++)
{
int fa;scanf("%d",&fa);
vt[fa].push_back(i);
}
dfs(1);
printf("%d\n",ans[1]);
return 0;
}
```