消防局的設立

問題描述

由題意知，及給定一顆樹，若節點內建立消防站，周圍兩個內均不需要建立消防站，問至少需要多少個消防站才能讓整個樹不發生不可控的火災？

思路

·f[x][0]：至少讓x向上2層之下都覆蓋信號的答案。
·f[x][1]：至少讓x向上1層之下都覆蓋信號的答案。
·f[x][2]：至少讓x自己及之下覆蓋信號的答案。
·f[x][3]：至少讓x向下1層之下都覆蓋信號的答案。
·f[x][4]：至少讓x向下2層之下都覆蓋信號的答案。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N=INT_MAX;
int n,f[1010][5];
vector<int> G[1010];
void dfs(int x) {
	if(G[x].empty()) {
		f[x][0]=1,f[x][1]=1,f[x][2]=1;
		return;
	}
	for(int i:G[x]) dfs(i);
	f[x][0]=1;
	int mi=N,mn=N;
	for(int i:G[x]){
		f[x][0]+=f[i][4];
		f[x][1]+=f[i][3];
		f[x][2]+=f[i][2];
		f[x][3]+=f[i][2];
		f[x][4]+=f[i][3];
		mi=min(mi,f[i][0]-f[i][3]);
		mn=min(mn,f[i][1]-f[i][2]);
	}
	f[x][1]+=mi;
	f[x][2]+=mn;
	f[x][1]=min(f[x][1],f[x][0]);
	f[x][2]=min(f[x][2],f[x][1]);
	f[x][3]=min(f[x][3],f[x][2]);
	f[x][4]=min(f[x][4],f[x][3]);
}
int main() {
	cin>>n;
	for(int i=2; i<=n; i++) {
		int u;
		cin>>u;
		G[u].emplace_back(i);
	}
	dfs(1);
	cout<<f[1][2];
}