[HNOI2003]消防局的设立

题目描述

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

输出文件仅有一个正整数，表示至少要设立多少个消防局才有能力及时扑灭任何基地发生的火灾。

思路：

这道题luogu上给的标签是DP，吓了我一跳

但实际上看完，才发现是一个树上的贪心

我们以1为根，遍历整棵树（只有n-1条边，所以一定是树）
然后这道题就变成了一个可行性问题

如果你想覆盖掉深度最深的点

你就必须把消防局建在他自己的位置上或者是他父亲或者是他爷爷的位置上

如果建在自己的位置上或者说是他父亲的位置上，这一定是亏本的

因为他自己深度最深（就是说一定是叶节点），所以不会有儿子之类的

你选他自己或他的父亲到会有冗余覆盖（覆盖了不存在的儿子和孙子），一定不是最优

所以我们每次找深度最大的点，在他爷爷那里建站即可

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define rii register int i
#define rij register int j
using namespace std;
struct bian{
    int to[1005],sl;
}x[1005];
struct dian{
    int sd,bh;
}y[1005];
int bj[1005],dad[1005],grp[1005],n,cnt;
void dfs(int wz,int fa,int gp)//预处理深度和父亲，爷爷
{
    dad[wz]=fa;
    grp[wz]=gp;
    for(rii=1;i<=x[wz].sl;i++)
    {
        if(x[wz].to[i]==fa)
        {
            continue;
        }
        y[x[wz].to[i]].sd=y[wz].sd+1;
        dfs(x[wz].to[i],wz,fa);
    }
}
void add(int wz,int sd)
{
    bj[wz]=1;
    if(sd==2)
    {
        return;
    }
    for(rii=1;i<=x[wz].sl;i++)
    {
        add(x[wz].to[i],sd+1);
    }
}
bool cmp(dian lk,dian kl)
{
    return lk.sd>kl.sd;
}
int main()
{
    scanf("%d",&n);
    for(rii=2;i<=n;i++)
    {
        int ltt;
        scanf("%d",&ltt);
        x[i].sl++; 
        x[i].to[x[i].sl]=ltt;
        x[ltt].sl++;
        x[ltt].to[x[ltt].sl]=i;
    }
    y[1].sd=1;
    for(rii=1;i<=n;i++)
    {
        y[i].bh=i;
    }
    dfs(1,0,0);
    sort(y+1,y+n+1,cmp);
    for(rii=1;i<=n;i++)
    {
        if(bj[y[i].bh]!=1)
        {
            cnt++;
            add(grp[y[i].bh],0);
        }
    }
    cout<<cnt;
}