****求助:数据1,数据9WA

#include<bits/stdc++.h>
using namespace std;
int n,dp[1005][5],u,v,mi=1000000;
vector <int> mp[1005];
void bfs(int x,int fa){
	if(mp[x].size()==1&&mp[x][0]==fa){
		dp[x][0]=1;
		dp[x][1]=1;
		dp[x][2]=1;
		dp[x][3]=0;
		dp[x][4]=0;
		return;
	}
	int s1=0,s2=0,s3=0,s4=0;
	for(int i=0;i<mp[x].size();i++){
		if(mp[x][i]!=fa){
			bfs(mp[x][i],x);
			s1+=dp[mp[x][i]][1];
			s2+=dp[mp[x][i]][2];
			s3+=dp[mp[x][i]][3];
			s4+=dp[mp[x][i]][4];
		}
	}
	for(int i=1;i<mp[x].size();i++){
		if(mp[x][i]!=fa){
			dp[x][1]=min(dp[x][1],s3-dp[mp[x][i]][3]+dp[mp[x][i]][0]);
			dp[x][2]=min(dp[x][2],s2-dp[mp[x][i]][2]+dp[mp[x][i]][1]);
		}
		dp[x][4]=s3; 
		dp[x][3]=s2;
		dp[x][0]=s4+1;
		dp[x][1]=min(dp[x][1],dp[x][0]);
		dp[x][2]=min(dp[x][2],dp[x][1]);
		dp[x][3]=min(dp[x][3],dp[x][2]);
		dp[x][4]=min(dp[x][4],dp[x][3]);
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=4;j++)dp[i][j]=1000000;
	}
	for(int i=2;i<=n;i++){
		cin>>u;
		mp[u].push_back(i);
		mp[i].push_back(u);
	}
	mp[1].push_back(0);
	bfs(1,0);
	for(int i=0;i<=2;i++)mi=min(mi,dp[1][i]);
	cout<<mi;
	return 0;
}

逻辑:以1为根，从叶节点出发向内，维护数组DP[i][j]表示此节点最近的子消防站 提交详情:https://www.luogu.com.cn/record/128855203