【每日一题】 4-8 黑白树
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);
} 
自愧不如
大疆公司氛围 166人发布