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

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

输入输出样例

输入 #1

6
1
2
3
4
5

输出 #1

2

分析

覆盖半径 $k=2$k=2。
树的每个节点都需要覆盖到。我们考虑深度最深的一个节点，他要被覆盖到，贪心的想，在能覆盖到它的前提下，消防局肯定能越高越好，因为能覆盖到的节点越多，总的消防局就会越少。
于是我们得到一种贪心思路：将每个点按深度从大到小排序，如果未被覆盖，每个点在它的爷爷处建立一个消防局，以此一直进行下去。就是将每个点入队，然后如果未被标记，就强行标记其他点就行了。
不过还有一种很棒的实现方法，不需要bfs啥的，但很需要理解。(我在洛谷上看到的hhh）
记 $o\left[i\right]$o[i] 表示 $i$i 最近的消防局离 $i$i 的距离，每次设消防局处 $o\left[i\right]=0$o[i]=0，然后往上一直更新 $k$k 个节点。每次判断 $i$i 是否被覆盖时，我们从 $i$i 一直往上找，来更新 $o\left[i\right]$o[i]。如果 $o\left[i\right[\&gt;k$o[i[>k，说明 $o\left[i\right]$o[i]未被覆盖到。可能有点抽象，让我画个图。
来看如图的树：

一开始建立的消防局和更新的区间如下：

蓝色为 $o\left[i\right]$o[i]的值。为什么不更新子树呢？
因为对于子树的点，我们往上找 $k$k 个父亲，肯定能找到一个消防局（因为这个消防局就是从深度最大的点来的）。还要注意我们处理的到的是一条直链，为什么得到直链就行？我们设立了一个消防局，对于兄弟节点到消防局的距离，我们显然可以通过其父亲节点的 $o\left[i\right]$o[i]来求得，因此我们得到直链，相当于得到了其他节点到该点的距离。
有不清楚之处，尽管提出啊！

下面贴代码：

#include <bits/stdc++.h>
#define N 1005
using namespace std;
struct node{
	int d, i;
	bool operator < (const node & A) const{
		return d > A.d;
	}
}e[N];
int f[N], o[N], ans;
int main(){
	int i, j, n, m, a, b, d, k = 2;
	scanf("%d", &n);
	e[1].d = 0, e[1].i = 1; o[1] = o[0] = 2 * N;
	for(i = 2; i <= n; i++){
		scanf("%d", &f[i]);
		e[i].d = e[f[i]].d + 1;
		e[i].i = i;
		o[i] = 2 * N;
	}
	sort(e + 1, e + i);
	for(i = 1; i <= n; i++){
		a = e[i].i;
		//printf("%d ", a);
		b = a;
		for(j = 1; j <= k; j++){
			b = f[b];
			o[a] = min(o[a], o[b] + j);
		}
		//printf("%d\n", o[a]) ;
		if(o[a] > k){
			o[b] = 0, ans++;
			a = b;
			for(j = 1; j <= k; j++){
				b = f[b];
				o[b] = min(o[b], o[a] + j);
			}
		}
	}
	printf("%d", ans);
	return 0;
}