正题之前
又是一道抓耳挠腮想了好久的好题， 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] +
\(k\) )
\(x\) 的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为 \(y\) 一定是选了），其他的儿子只需要覆盖的自己的儿子即可
- dp[x][2] = min ( dp[y][1] +
有一个儿子覆盖到父亲，但无法覆盖到 \(y\) 的兄弟，所以其他儿子要覆盖到自己
- dp[x][3] =
让每个儿子覆盖到自己
- dp[x][4] =
让每个儿子覆盖到自己的儿子
遍历顺序
由叶子节点到根
边界条件
- 叶子节点
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;
}