是一道非常有意思的。。。。乱搜题
打了个树形dp，将自己的建，不建，次建作为状态
f[nx][0]=min(f[nx][0],f[v][2]);
f[nx][0]=min(f[nx][0],f[v][1]);//0为不建，从1建和2借建来
f[nx][1]=min(f[nx][1],f[v][0]+1);
f[nx][1]=min(f[nx][1],f[v][2]+1);//1为建，
f[nx][1]=min(f[nx][1],f[v][1]+1);
f[nx][2]=min(f[nx][2],f[v][1]);//2为借建
发现没有考虑两个兄弟的情况，然后题解的dp和我的意义完全不一样，我就又写了个贪心：每次找最深的点，在它爷爷上建一个，进行覆盖。最大的收获是fa【i】的使用，利用了树只有一个父亲（指定根），非常便利地找爷爷。也方便上下覆盖，
include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector <int> son[1002];
int maxn,ans,deep[1002],fa[1002],n;
bool vis[1002];
void dfs(int nx,int d){
vis[nx]=1;
if(d==0) return;
int si=son[nx].size();
for(int i=0;i<si;i++){
int v=son[nx][i];
dfs(v,d-1);
}
dfs(fa[nx],d-1);
}
int main(){
scanf("%d",&n);
fa[1]=1;
for(int i=2;i<=n;i++){
int opt;
scanf("%d",&opt);
// son[i].push_back(opt);
son[opt].push_back(i);
fa[i]=opt;
}
for(int i=1;i<=n;i++)
deep[i]=deep[fa[i]]+1;
while(1){
int fl=0;
for(int i=1;i<=n;i++)
if(vis[i]==0&&deep[i]>deep[fl]) fl=i;
if(fl==0) break;
dfs(fa[fa[fl]],2);
ans++;
}
printf("%d",ans);
return 0;
}