贪心取代树形DP

/**************************************************************
    Problem: 1217
    User: lxy8584099
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:860 kb
****************************************************************/
 
/*
好文！
https://blog.csdn.net/niiick/article/details/80744826
可以扩展出距离k的求解模型 
贪心做法 每次找到最深的点a 往上走k步到b 选择b建立消防站 然后b往外扩k的距离
这样可以确保b以下（更深）的节点被包括到 同时又可以更新一下b以上的一些答案
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1050;
int f[N],n;
struct pp {int v,nxt;} e[N<<1];
struct point {int id,dep;} p[N];
int head[N],tot=1,fa[N];
void add(int u,int v) {e[++tot].nxt=head[u];head[u]=tot;e[tot].v=v;} 
bool cmp(point a,point b) {return a.dep>b.dep;} 
void dfs(int u,int la)
{
    for(int j=head[u];j;j=e[j].nxt)
    {
        int v=e[j].v; if(v==la) continue;
        fa[v]=u; p[v].dep=p[u].dep+1;
        dfs(v,u);
    }
}
void update(int u)
{
    if(!f[u]) return ;
    for(int j=head[u];j;j=e[j].nxt)
    {
        int v=e[j].v;
        if(f[v]<f[u]-1) f[v]=f[u]-1,update(v);
// 判断一下v是否有了更好的update执行过
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=2,x;i<=n;i++)
        scanf("%d",&x),add(x,i),add(i,x),p[i].id=i;
    fa[1]=p[1].id=p[1].dep=1;dfs(1,0);
    sort(p+1,p+n+1,cmp);
    memset(f,-1,sizeof(f));
    int ans=0;
    for(int i=1;i<=n;i++) if(f[p[i].id]==-1)
    {
        int u=p[i].id;ans++;
        for(int j=1;j<=2;j++) u=fa[u];
        f[u]=2; update(u);
    }
    printf("%d\n",ans);
    return 0;
}