一、题意理解

我们有一棵以 $1$ 为根的有根树，每个节点 $i$ 有一个参数 $k_i$。

一次操作：选择一个白色节点 $i$，将 $i$ 到根的路径上距离 $i$ 小于 $k_i$ 的所有节点染黑（包括 $i$ 本身）。

目标：用最少的操作次数染黑整棵树。

---

二、样例分析

样例：

n=4
父节点：2的父亲是1，3的父亲是2，4的父亲是1
k = [1, 2, 2, 1]

树结构：

    1
   / \
  2   4
  |
  3

k值：

• 节点1: k=1
• 节点2: k=2
• 节点3: k=2
• 节点4: k=1

---

操作方案

1. 选择节点3（白色），k=2，覆盖节点3、2、1（距离3：0<2，距离2：1<2，距离1：2不小于2？等等，距离计算是到节点i的距离，不是到根的距离。题目说：i到根的链上所有与节点i距离小于k_i的点。这里“与节点i距离”指的是在路径上到i的步数。）

   仔细读题："i 到根的链上（包括节点 i 与根）所有与节点 i 距离小于 k_i 的点"

   距离是沿着链到 i 的步数：

   • 对于节点3：链是 3-2-1
     • 节点3：距离0 < 2 → 染黑
     • 节点2：距离1 < 2 → 染黑
     • 节点1：距离2 < 2？否 → 不染黑 所以操作3只染黑3和2。

2. 选择节点4：链4-1

   • 节点4：距离0 < 1 → 染黑
   • 节点1：距离1 < 1？否 → 不染黑 所以操作4只染黑4。

3. 选择节点1：链1

   • 节点1：距离0 < 1 → 染黑

总共3次操作。

---

三、关键观察

一次操作选择节点 $u$，会染黑 $u$ 到根路径上距离 $u$ 小于 $k_u$ 的点，即从 $u$ 往上走最多 $k_u-1$ 步能到达的点（包括 $u$ 本身）。

换句话说，操作 $u$ 能覆盖从 $u$ 往上 $k_u$ 个节点（包括 $u$）。

---

四、问题转化

我们要选择若干个节点，使得每个节点都被某个操作覆盖。

对于节点 $v$，能被哪些 $u$ 覆盖？

• $u$ 必须在 $v$ 的子树中（因为操作时 $u$ 必须白色，但这里其实不要求白色？不对，题目要求操作时 $u$ 是白色，但我们可以按任意顺序执行，所以顺序重要。但最小操作次数与顺序无关，因为一个节点操作一次就永久变黑，我们可以从深到浅操作。）

实际上，我们可以从叶子往根考虑，这是一个贪心覆盖问题。

---

五、贪心策略

我们从叶子往根处理，当遇到一个节点还没有被覆盖时，我们必须选择它的某个后代（或它自己）来覆盖它。

为了最大化覆盖范围，我们应选择能覆盖到最上面的操作节点。

设 $dp[u]$ 表示在 $u$ 的子树中，已经进行的操作能覆盖到 $u$ 上方多少距离（即从 $u$ 往上还能额外覆盖多少层）。如果 $dp[u] \ge 1$，说明 $u$ 已被覆盖。

初始 $dp[u]=0$ 表示未被覆盖。

---

当我们发现 $u$ 未被覆盖（即 $dp[u]=0$）时，我们必须进行一次操作。为了覆盖 $u$，我们可以在 $u$ 的某个后代 $v$ 操作，$v$ 的 $k_v$ 要足够大，能覆盖到 $u$。

但为了减少操作次数，我们应选择能覆盖尽可能多上方节点的操作。

实际上，我们可以维护 $f[u]$ 表示在 $u$ 的子树中，如果我们在子树内操作，能覆盖到 $u$ 上方的最远距离（即 $\max_{v \in subtree(u)} (k_v - dist(u,v))$），其中 $dist(u,v)$ 是 $u$ 到 $v$ 的步数。

---

算法步骤：

1. DFS 后序遍历树。
2. 维护 $f[u] = \max(0, \max_{v \in subtree(u)} (k_v - dist(u,v)))$。
3. 同时维护 $g[u]$ 表示从 $u$ 的祖先的操作能覆盖到 $u$ 下方的最远距离（即从上面传下来的覆盖能力）。
4. 当 $g[u] = 0$ 且 $f[u] > 0$ 时，说明 $u$ 未被上方覆盖，但子树内有节点能覆盖 $u$，此时我们选择那个能覆盖最远的节点（即 $f[u]$ 对应的节点）进行操作，答案加1，并更新 $g$ 值。

---

更简单的做法（常见解法）：

设 $up[u]$ 表示在 $u$ 的子树中，已选的操作能覆盖到 $u$ 上方的最大距离（初始0）。 设 $down[u]$ 表示在 $u$ 的子树中，某个操作节点能覆盖到 $u$ 上方的最大距离（即 $\max(0, \max_{v \in subtree(u)} (k_v - dist(u,v)))$）。

DFS 过程：

• 计算 $down[u] = \max( down[v] - 1, k_u - 1 )$ 对 $v \in children(u)$ 取最大值，再与0取max。
• 计算 $up[u] = \max( up[v] - 1 )$ 对 $v \in children(u)$ 取最大值。
• 如果 $up[u] = 0$ 且 $down[u] > 0$，说明需要新操作，答案+1，并令 $up[u] = down[u]$。

这样 $up[u]$ 表示当前节点被子树内操作覆盖后，还能往上覆盖多少层。

---

六、正确性解释

• $down[u]$ 表示如果在 $u$ 的子树内进行操作，能覆盖到 $u$ 上方的最远距离。
• $up[u]$ 表示 $u$ 是否已被覆盖，并且能往上覆盖多远。
• 当 $up[u] = 0$ 时，$u$ 未被覆盖，必须在其子树内进行一次操作，我们选择能覆盖最远的那个操作（即 $down[u]$ 对应的操作），然后 $up[u]$ 记录这个覆盖能力。

---

七、算法步骤

1. 建树，读入 $k$。
2. DFS 后序遍历：
   • $down[u] = \max(0, k_u - 1, \max_{v \in children(u)} (down[v] - 1))$
   • $up[u] = \max_{v \in children(u)} (up[v] - 1)$
   • 如果 $up[u] == 0$ 且 $down[u] > 0$：
     • $ans{+}{+}$
     • $up[u] = down[u]$
3. 输出 $ans$。

---

八、样例验证

样例： 树：1(2,4), 2(3), 3(), 4() k: 1:1, 2:2, 3:2, 4:1

DFS：

• 节点3: down= max(0, 2-1, []) = 1, up=0 → up=0且down>0 → ans=1, up=1
• 节点4: down= max(0, 1-1, []) = 0, up=0 → 不操作
• 节点2: down= max(0, 2-1, 1-1=0) = 1, up= max(1-1=0) = 0 → up=0且down>0 → ans=2, up=1
• 节点1: down= max(0, 1-1, 1-1=0, 0-1=-1) = 0, up= max(1-1=0, 0-1=-1) = 0

---

修正： 如果 $up[u] = 0$：

• 如果 $down[u] > 0$，用 down 对应操作，ans+1, up=down
• 否则（down=0），必须在 $u$ 操作，ans+1, up = k_u - 1

---

九、修正算法

设 $cover[u]$ 表示 $u$ 被覆盖后（或被祖先覆盖）能往上覆盖的最远距离。 设 $best[u]$ 表示 $u$ 的子树中能覆盖到的最远祖先距离（即 $\max_{v \in subtree(u)} (k_v - dist(u,v))$）。

DFS：

• $best[u] = \max( k_u, \max_{v \in children(u)} (best[v] - 1) )$
• 如果 $cover[u] = 0$ 且 $best[u] > 0$，则需要在 $u$ 的子树内选择一个节点操作，选择能提供 $best[u]$ 的那个节点，然后 $cover[u] = best[u]$，ans+1
• 将 $cover[u] - 1$ 传递给孩子们：对每个孩子 $v$，$cover[v] = \max(cover[v], cover[u] - 1)$

这样 $cover[u]$ 表示 $u$ 被覆盖后还能往上覆盖多少，初始0。

---

十、最终代码（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

struct edge {
    int to, next;  // 子节点to，下一个子节点的索引
} e[N << 1]; // 存储树的边

int cnt, head[N];  // cnt：边计数器；head[u]：u的子节点链表头
int n, k[N], ans, fa[N];  // fa：父节点；ans：操作次数

// 添加边：u -> v（u是v的父节点）
inline void add(int u, int v) {
    e[++cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt;
}

// 后序遍历处理节点u
inline int dfs(int u) {
    int ret = 0;  // 子节点能覆盖到u的最大范围

    // 递归处理所有子节点
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        ret = max(ret, dfs(v));  // 取子节点的最大覆盖范围
    }

    // 子节点无法覆盖u，需操作u
    if (ret <= 0) {
        ans++;  // 操作次数+1
        return k[u] - 1;  // u的操作能覆盖父节点方向k[u]-1步
    }

    // 子节点可覆盖u，更新父节点的k值（扩大覆盖范围）
    k[fa[u]] = max(k[fa[u]], k[u] - 1);
    return ret - 1;  // 覆盖范围向上递减1
}

int main() {
    scanf("%d", &n);

    // 读入2~n号节点的父节点，构建树
    for (int i = 2, x; i <= n; i++) {
        scanf("%d", &fa[i]);
        add(fa[i], i);  // 父节点->子节点建边
    }

    // 读入每个节点的k值
    for (int i = 1; i <= n; i++) {
        scanf("%d", &k[i]);
    }

    // 从根节点开始处理
    dfs(1);
    printf("%d\n", ans);
    return 0;
}

---

十一、总结

本题的关键在于：

1. 理解操作覆盖的范围：从操作节点 $u$ 往上 $k_u$ 个节点。
2. 使用贪心策略，从根到叶子传递覆盖信息，当节点未被覆盖时，在子树内选择能覆盖最远的操作。
3. 通过 DFS 维护两个值：子树能提供的最佳覆盖能力和当前节点的覆盖状态。 4.该解法时间复杂度 $O(n)$，可以处理 $n \le 10^5$ 的数据范围。