正題之前

又是一道抓耳撓腮想了好久的好題， AC 了之後，感覺自己的思想又得到了洗禮 QwQ ，第一次寫題解，有錯望老師見諒

題目傳送門

思路

因為題目求的是覆蓋樹上所有點的所放置最少的消防站數量，因此此題需使用樹形 DP 解決

狀態申明

因為每個"消防局"能覆蓋與它距離不超過 2 的節點 ，因此
總共設有5個狀態

• dp[x][0] 為覆蓋到 \(x\) 的爺爺（包括父親）和 \(x\) 整棵子樹的最少個數；
• dp[x][1] 為覆蓋到 \(x\) 的父親和 \(x\) 整棵子樹的最少個數；
• dp[x][2] 為覆蓋 \(x\) 整棵子樹的最少個數；
• dp[x][3] 為覆蓋所有 \(x\) 的兒子及其子樹的最少個數；
• dp[x][4] 為覆蓋所有 \(x\) 的孫子及其子樹的最少個數；

狀態轉移方程

• dp[x][0] = 1 \(+\) dp[y][4] （ \(y\) 為 \(x\) 的孩子 ）

要覆蓋到爺爺的話必須選 \(x\) ，並貪心地選 \(y\) 的第五種狀態

• dp[x][1] = min ( dp[y][0] + dp[k][3] )（ \(y\) 和 \(k\) 皆為 \(x\) 的孩子且 \(y\) \(k\) )

\(x\) 的兒子中有一個一定覆蓋的爺爺，同時覆蓋到兄弟（因為 \(y\) 一定是選了），其他的兒子只需要覆蓋的自己的兒子即可

• dp[x][2] = min ( dp[y][1] + dp[k][2] )（ \(y\) 和 \(k\) 皆為 \(x\) 的孩子且 \(y\) \(k\) )

有一個兒子覆蓋到父親，但無法覆蓋到 \(y\) 的兄弟，所以其他兒子要覆蓋到自己

• dp[x][3] = dp[y][2] （ \(y\) 為 \(x\) 的孩子 ）

讓每個兒子覆蓋到自己

• dp[x][4] = dp[y][3] （ \(y\) 為 \(x\) 的孩子 ）

讓每個兒子覆蓋到自己的兒子

遍歷順序

由葉子節點到根

邊界條件

• 葉子節點

dp[x][0] = dp[x][1] = dp[x][2] =1 ;
dp[x][3] = dp[x][4] = 0 ;

• 非葉子節點

dp[x][0] = 1 , dp[x][1] = dp[x][2] = \(\infty\) ;
dp[x][3] = dp[x][4] = 0 ;

輸出答案

dp[1][2]（根包含自己和所有子樹的最小答案）

評估效率

時間複雜度：\(O (n)\) $ \ \ \ \ $ 空間複雜度：\(O (n)\)

注意

因為 dp[x][0] 的答案包含 dp[x][1 ~ 4] , dp[x][1] 的答案包含 dp[x][2 ~ 4]。同理，因此 dp[x][4] \(\le\) dp[x][3] \(\le\) dp[x][2] \(\le\) dp[x][1] \(\le\) dp[x][0] , 但如果 dp[x][i] < dp[x][i+1]，因此就該跟新 dp[x][i+1] 。

AC代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF=1e18;
ll n,y,dp[1005][5];
vector<ll>t[100005];
void dfs(ll x,ll fa){
	ll cnt=0,s2=0,s3=0;
	for(auto y:t[x]){
		if(y==fa) continue;
		dfs(y,x);
		s2+=dp[y][2];
		s3+=dp[y][3];
		cnt++;
	}
	if(!cnt){
		dp[x][0]=dp[x][1]=dp[x][2]=1;
		dp[x][3]=dp[x][4]=0;
		return;
	}
	dp[x][0]=1;dp[x][1]=dp[x][2]=INF;
	dp[x][3]=0;dp[x][4]=0;
	for(auto y:t[x]){
		if(y==fa) continue;
		dp[x][0]+=dp[y][4];
		dp[x][1]=min(dp[y][0]+s3-dp[y][3],dp[x][1]);
		dp[x][2]=min(dp[y][1]+s2-dp[y][2],dp[x][2]);
		dp[x][3]+=dp[y][2];
		dp[x][4]+=dp[y][3];
	}
	for(int i=1;i<5;i++)
		dp[x][i]=min(dp[x][i],dp[x][i-1]);
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>y;
		t[i+1].push_back(y);
		t[y].push_back(i+1);
	}
	dfs(1,0);
	cout<<dp[1][2];
	return 0;
}