DP好题，贪心好题。
传送门：GO
参考了一下rickole大大的题解：GO
用f[u][0/1/2/3/4]表示第u个点能管+2，+1，0，-1，-2层的最小消防局个数。
其余可以画个图yy一下。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int read(){ 4 int x=0,f=1; 5 char c=getchar(); 6 while(!isdigit(c)){ 7 if(c=='-') f=-1; 8 c=getchar(); 9 } 10 while(isdigit(c)){ 11 x=x*10+c-'0'; 12 c=getchar(); 13 } 14 return x*f; 15 } 16 const int N=2010; 17 const int inf=1e9; 18 int n,cnt; 19 int f[N][5]; 20 int head[N<<1]; 21 struct edge{int to,next;}e[N<<1]; 22 void addedge(int from,int to){e[++cnt]=(edge){to,head[from]};head[from]=cnt;} 23 void dfs(int u){ 24 f[u][0]=1; 25 f[u][3]=f[u][4]=0; 26 for(int i=head[u];i;i=e[i].next){ 27 int v=e[i].to; 28 dfs(v); 29 f[u][0]+=f[v][4]; 30 f[u][3]+=f[v][2]; 31 f[u][4]+=f[v][3]; 32 } 33 if(!head[u]) f[u][1]=f[u][2]=1; 34 else{ 35 f[u][1]=f[u][2]=inf; 36 for(int i=head[u];i;i=e[i].next){ 37 int v=e[i].to; 38 int a=f[v][0],b=f[v][1]; 39 for(int j=head[u];j;j=e[j].next){ 40 if(i==j) continue; 41 int w=e[j].to; 42 a+=f[w][3]; 43 b+=f[w][2]; 44 } 45 f[u][1]=min(f[u][1],a); 46 f[u][2]=min(f[u][2],b); 47 } 48 } 49 for(int i=1;i<=4;i++){ 50 f[u][i]=min(f[u][i],f[u][i-1]); 51 } 52 } 53 int main(){ 54 n=read(); 55 for(int i=2;i<=n;i++){ 56 addedge(read(),i); 57 } 58 dfs(1); 59 printf("%d",f[1][2]); 60 return 0; 61 }
个人认为本题贪心写法更具有亮点：
BJpers2大大的题解：GO
简单来说，就是叶子节点的爷爷一定是消防局，按照深度向祖父取点，计算覆盖。
先处理出深度，排序，用一个数组处理一下。
另外这个解法普适性很强，可以解决一些路径覆盖的问题。
因为这题不会做，以上是看题解得到的一些收获。