消防局的设立

消防局的设立

问题描述

由题意知，及给定一颗树，若节点内建立消防站，周围两个内均不需要建立消防站，问至少需要多少个消防站才能让整个树不发生不可控的火灾？

思路

·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];
}