https://ac.nowcoder.com/acm/problem/13249

题意:

给一棵树，每个点有一个值 k[i]，表示取这个点的话可以将这个点到根节点的所有点里，例句这个点距离小于 k[i] 的点变成黑色，求所有点都变成黑色最少取几个点。

解法：

贪心，从根节点向上遍历，如果这个结点的值等于0，那么我们取这个点，反之，不取这个点
所以维护一个数组 a，表示还能取的点的个数，然后遍历的同时维护一下即可。

注意可能存在取已经被染成黑色的结点，比如

贪心的话，首先取 4 号点，然后可以覆盖 3 号点，然后取 2 号点和 1 号点，但实际上我们取 4 号点和 3 号点即可。
所以在遍历的同时，再维护一个子树的最大  (k 值 - 到子树根节点距离) 即可 
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
struct edge
{
	int to;
	int nex;
}e[MAXN * 2];
int head[MAXN], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
int k[MAXN], a[MAXN];
int ans;
void dfs(int u, int fa)
{
	a[u] = 0;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int v = e[i].to;
		if (v == fa)
			continue;
		dfs(v, u);
		a[u] = max(a[u], a[v] - 1);
		k[u] = max(k[u], k[v] - 1);
	}
	if (a[u] == 0)
	{
		ans++;
		a[u] = k[u];
	}
}
int main()
{
	init();
	int n;
	sc("%d", &n);
	for (int i = 2; i <= n; i++)
	{
		int t;
		sc("%d", &t);
		add(i, t);
		add(t, i);
	}
	for (int i = 1; i <= n; i++)
		sc("%d", &k[i]);
	dfs(1, 0);
	pr("%d", ans);
}