题目链接

https://www.luogu.com.cn/problem/P2279

思路

我们令$dp[i][state]$表示节点$i$在$state$状态下，消防站的最小数量。

对于dp方程的定义如下：

$dp[i][0]$表示可以覆盖到从节点i向上2层的最小消防站个数，$dp[i][1]$表示可以覆盖到从节点i向上1层的最小消防站个数，$dp[i][2]$表示可以覆盖到从节点i向上0层的最小消防站个数，$dp[i][3]$表示可以覆盖到从节点i向下1层的最小消防站个数，$dp[i][4]$表示可以覆盖到从节点i向下2层的最小消防站个数。

显然，$dp[i][0]\ge dp[i][1]\ge dp[i][2]\ge dp[i][3]\ge dp[i][4]$。

对于$dp[i][0]$：$dp[i][0]=1+{\sum }_{s\in son(i)}dp[s][4]$。

对于$dp[i][1]$：$dp[i][1]=min(dp[i][1],dp[s][0]+{\sum }_{t\in son(i)}dp[t][3])(s\in son(i)\&\&t\ne s)$。

对于$dp[i][2]$：$dp[i][2]=min(dp[i][2],dp[s][1]+{\sum }_{t\in son(i)}dp[t][2])(s\in son(i)\&\&t\ne s)$

对于$dp[i][3]$：$dp[i][3]={\sum }_{s\in son(i)}dp[s][2]$。

对于$dp[i][4]$：$dp[i][4]={\sum }_{s\in son(i)}dp[s][3]$。

最后的答案即为：$dp[1][2]$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e3 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;int n;
int dp[N][5];
vector<int>mp[N];
void dfs(int u)
{dp[u][0] = 1;vector<int>v(5, 0);for (int j : mp[u]){	dfs(j);for (int i = 0; i < 5; i++)v[i] += dp[j][i];}dp[u][0] += v[4], dp[u][3] += v[2], dp[u][4] += v[3];dp[u][1] = dp[u][2] = inf;for (int j : mp[u]){dp[u][1] = min(dp[u][1], dp[j][0] + v[3] - dp[j][3]);dp[u][2] = min(dp[u][2], dp[j][1] + v[2] - dp[j][2]);}for (int i = 1; i <= 4; i++)dp[u][i] = min(dp[u][i], dp[u][i - 1]);
}
void solve()
{cin >> n;for (int i = 1, fa; i < n; i++){cin >> fa;mp[fa].push_back(i + 1);}dfs(1);cout << dp[1][2] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}