• 题目描述

  一棵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)

• 样例解释:

  对节点3操作，导致节点2与节点3变黑
  对节点4操作，导致节点4变黑
  对节点1操作，导致节点1变黑
  无序列表内容

• 输出描述:

  一个数表示最少操作次数

解题思路

题目一上手，可以简单画个图，通过树图，发现最后一个点是必选的，那叶子节点上方的点我们应该选择那些点呢？是不是选择叶子节点长度够不到的点就选呢？不是的，我们可以假设叶子节点k=3，它父节点k=10,其余节点k值都是1，上方贪心方法直接裂开。不过我们还是可以通过这个错误的贪心方法发现问题，加以修改就是我们正确的贪心攻略。对于每一个节点我们要维护题目中的k数组表示子节点到目前节点往上可以走最远的距离，也要新开辟一个f数组，维护来自子节点往上最远的覆盖距离，当这个覆盖距离为0时，说明这个点无法覆盖，我们需要新增一个节点，我们选取的点应该是越过这个点可以往上走最远的节点涂黑。

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 1e5 + 7;
vector<int> p[N];
int k[N], f[N]; //需要维护的2个数组
int ans;

void dfs(int x, int fa) {
    for (int i = 0; i < p[x].size(); ++i) {
        int u = p[x][i];
        dfs(u, x); //注意k数组，我们不关心这个最远来自谁，只要知道可以最远多少就行了
        k[x] = max(k[x], k[u] - 1); //维护k[x] 是保持还是子节点消耗1，更新取max
        f[x] = max(f[x], f[u] - 1); // 还可以往上延申长度
    }
    if (!f[x]) { //如果子节点都无法覆盖到这个点
        ++ans; //选取这个点
        f[x] = k[x]; //更新这个点的f[x]
    }
}

int main() {
    int n = read();
    for (int i = 2; i <= n; ++i) {
        int u = read();
        p[u].push_back(i); // = = 注意这个父子关系别搞反了
    }
    for (int i = 1; i <= n; ++i)    k[i] = read();
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}