题目描述
2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。
由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。
你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。
输入输出格式
输入格式：
输入文件名为input.txt。
输入文件的第一行为n （n<=1000），表示火星上基地的数目。接下来的n-1行每行有一个正整数，其中文件第i行的正整数为a[i]，表示从编号为i的基地到编号为a[i]的基地之间有一条道路，为了更加简洁的描述树状结构的基地群，有a[i]<i。
输出格式：
输出文件名为output.txt
输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。
输入输出样例
输入样例#1：
复制
6
1
2
3
4
5
输出样例#1：
复制
2一开始以为是简单地树形DP，一头撞死后参考大佬题解才发现贪心来着（树形DP也可以但是贪心更简单）明确怎么贪，对于每一棵树，它最深的节点肯定是要被覆盖的，我们从这里入手；对于一个最深的节点来说，可以在它这里建一个消防站，也可以在它的父亲那里建一个消防站，还可以在它祖父那里建一个消防站，不难想到，在祖父处建一个消防站就可以覆盖最多的节点，由于是从最底层开始的，满足贪心的性质，策略成立那怎么判断一个点是否被覆盖呢，对于本题中的每一个点，可以覆盖它的节点有：它的祖父，它的父亲，它的兄弟，它的儿子，它的孙子，除了兄弟之外的情况都可以用f[]数组来维护，那该怎么处理兄弟的情况呢？我们引入一个o数组,o[i]表示里i距离最近的消防站到i的距离，当一个节点的o[父亲]==1时，它一定被覆盖，这样就解决了兄弟的问题详见代码注释完整代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=
1005;
int b[MAXN],o[MAXN],d[MAXN],f[MAXN],n,ans,u,fa,ffa;//u,fa,ffa分别表示当前节点，它的父亲，它的祖父
bool cmp(
int i,
int j){
return d[i]>
d[j];}
int main()
{
scanf("%d",&
n);
b[1]=
1;o[
1]=o[
0]=
0x3f;d[
1]=
0;//可以发现有没有根对这个问题影响不大，转化为无根树
for(
int i=
2;i<=n;i++)scanf(
"%d",&f[i]),d[i]=d[f[i]]+
1,b[i]=i,o[i]=
0x3f;
sort(b+
1,b+n+
1,cmp);//按深度排序
for(
int i=
1;i<=n;i++
)
{
u=b[i];fa=f[u];ffa=
f[f[u]];//依次取出
o[u]=min(o[u],min(o[fa]+
1,o[ffa]+
2));//用当前节点的父亲和祖父更新o[]数组
if(o[u]>
2)//o[u]>2的话说明没有消防站可以覆盖到当前节点
{
ans++;o[ffa]=
0;//在它的祖父处新建一个消防站
o[f[ffa]]=min(o[f[ffa]],
1);o[f[f[ffa]]]=min(o[f[f[ffa]]],
2);//向上更新它的父亲和祖父
}
}
cout<<
ans;//愉快的输出
return 0;
}
参考大佬@BJpers2 的题解
转载于:https://www.cnblogs.com/pcpcppc/p/9807800.html
相关资源：各显卡算力对照表！
