【每日一题】黑白树
黑白树
https://ac.nowcoder.com/acm/problem/13249
题目
题目描述：一棵n个点的有根树，1号点为根，相邻的两个节点之间的距离为1。树上每个节点i对应一个值k[i]。每个点都有一个颜色，初始的时候所有点都是白色的。
你需要通过一系列操作使得最终每个点变成黑色。
每次操作需要选择一个节点i，i必须是白色的，然后i到根的链上（包括节点i与根）所有与节点i距离小于k[i]的点都会变黑，已经是黑的点保持为黑。
问最少使用几次操作能把整棵树变黑。
第一行一个整数n (1 ≤ n ≤ 10^5)
接下来n-1行，每行一个整数，依次为2号点到n号点父亲的编号。
最后一行n个整数为k[i] (1 ≤ k[i] ≤ 10^5)
一个数表示最少操作次数
解析
先提示一下：这道题是树+贪心。
说实话我一开始没想到这道题可以贪心，我还以为是树上dp之类的，但是我不太会写。
但是重要的是，我们只要知道这道题的贪心策略之后，这道题就简单了不少：
贪心策略排除：
- 我们按照常规思想，我们的贪心策略可能会有两种。一个是选出里面最大的优先操作；另一个就是从叶往根逐步删除。
- 首先这种题目就不可能给你这么简单的操作，这两种可以排除了。但我还是来讲一下原因：
- 直接选最大的操作都难，但是我们的操作思想确实与这个有关：这里直接来的话，如果有大到多余的（大，但离根进），很可能就会浪费。
- 那如果逐步删除呢？这个一想就知道不可能，如果浪费了权值大的项岂不是很亏？
本题贪心策略：
- 补充一句：这道题只能对上面进行染色，这是整个算法非常重要的一点。
- 这道题的贪心策略呢，我已经排除了上面两种，不如换个角度来看。我们不管是选最大的操作，还是逐步删除，都是在选择起点操作。
- 我们举个例子：某个点要是被下面其他点变黑，当然是好事，可以减少操作次数。但是好和更好的差别在哪呢？在于影响到这个点的操作还阔以影响什么更多的点。
- 这就是我们在操作终点。总结下来就是：我们对某一点最好的是：既满足这一点被染黑的需求，并且可以染黑上面更多的点。
- 很多思想都是在对终点进行操作，或者说是在用最后的小问题，解决一直到达根部的大问题。
咋操作嘞：
- 我们在这里有一个思想：我们起点对上面有作用，但是终点不管起点是哪个，只要我们贪心策略的作用大就好。
- 所以我们就可以认为某一个节点的权值就是其大权子节点减一。举个例子就是：父节点为2，子节点为8，在对更上面节点的作用中，我们可以认为这个父节点就是7（8 - 1）。
- 假如我们已经知道了每个节点可以最大表示的权值（就是根据第二点转换的）是多少。现在我们一个根有多个子节点，选出可以染色最远的向上走就行了。
- 所以我们有了两个问题。一个是要求每个起点可以表示的权值；另一个是所有点都染不到色的点怎么办。
- 首先是起点表示的权值，我们一样可以利用dfs用底至上进行计算：每个节点的最大值表示权就是：自己和子节点减一中的最大值。k[u] = max(k[u], k[v] - 1)。
- 然后是染不到色的节点，我们可以判断出来，然后给他赋予当前节点最大可染色距离。
- 为了第六点，我们添加一个数组f，单纯的表示最大的染色距离，使其到蔓延终点以后无法更新，停下来（此时f[u] == 0）。
- 然后让f[u] = f[k]（赋值最大蔓延距离），循环上去。（根节点就是一个无法蔓延节点，我们就会计数）
打代码咯：
- 老方法，前向星保存树，主要是用习惯了前向星，发现真好用哈哈哈哈。
- 该存的存好了以后就可以进入dfs了。
- dfs过程没有很多再去描述的了，记得在蔓延结束时计数就好了。（详情看上面的算法讲解）
- 那就看代码吧？哈哈
AC代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
//代码预处理区
const int MAX = 1e5 + 7;
int head[MAX], tot;
struct Node {
int v, next;
} edge[MAX << 1];
int n, k[MAX];
int f[MAX], cnt;
//全局变量区
template<class T>inline void read(T& res);
void add_edge(int u, int v);
void dfs(int u, int fa);
//函数预定义区
int main() {
read(n);
tot = 0; memset(head, 0, sizeof head);
for (int i = 2; i <= n; i++) {
int v; read(v);
add_edge(i, v);
add_edge(v, i);
}
for (int i = 1; i <= n; i++) read(k[i]);
cnt = 0; memset(f, 0, sizeof f);
dfs(1, 0);
printf("%d\n", cnt);
return 0;
}
template<class T>inline void read(T& res) {
char c; T flag = 1;
while ((c = getchar()) < '0' || c > '9')
if (c == '-')
flag = -1;
res = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
res = res * 10 + c - '0';
res *= flag;
}
void add_edge(int u, int v) {
tot++;
edge[tot].v = v;
edge[tot].next = head[u];
head[u] = tot;
}
void dfs(int u, int fa) {
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].v;
if (fa == v) continue;
dfs(v, u);
f[u] = max(f[u], f[v] - 1);
//筛选出所有分支中能延伸的最大值
k[u] = max(k[u], k[v] - 1);
//更新每个节点可以表示的最大延伸值
}
if (!f[u]) {
cnt++;
f[u] = k[u];
}
//u节点不被子节点覆盖，就从该节点重新操作
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
投递快手等公司10个岗位 >