路径覆盖 题解

题目分析

我们有一棵以 $1$ 为根的有根树，初始所有结点都是白色的。现在需要选择一些结点染成黑色，要求每一条从叶子到根结点的路径上都至少有一个黑色结点。每个结点 $i$ 染色需要代价 $c_i$，目标是最小化总代价。

叶子定义为没有子结点的结点。题目保证输入中父结点编号小于子结点编号，即 $f_i<i$，这给自底向上的递推提供了极大便利。

解题思路

本题的核心是树形 DP。我们需要对每个子树计算一个最优代价，使得该子树内的叶子到该子树根结点的路径上都有黑点。然后通过合并子树信息，并考虑在根结点染色，得到整棵树的答案。

状态定义

设 $ans[i]$ 表示：在结点 $i$ 的子树中，满足所有叶子到结点 $i$ 的路径上至少有一个黑色结点的最小染色代价。

需要注意的是，$ans[i]$ 并不要求结点 $i$ 本身被染色，只要求路径（以叶子为起点，结点 $i$ 为终点）上存在黑点。

状态转移

1. 叶结点（没有子结点）
   它的子树只包含自己，路径就是结点 $i$ 本身。为了满足要求，必须把 $i$ 染色，因此：
   [
   ans[i] = c_i
   ]

2. 非叶结点
   结点 $i$ 可能有若干个子结点。根据我们在结点 $i$ 是否染色，分两种情况：

   • 不在 $i$ 染色：那么每个子结点 $j$ 的子树必须各自满足条件，且黑点也会自然覆盖从叶子到 $i$ 的路径（因为路径经过 $j$）。此时总代价为所有子结点 $ans[j]$ 之和。
   • 在 $i$ 染色：此时从任意叶子到 $i$ 的路径上都有黑点 $i$，因此所有子树的内部都不再需要额外的黑点。总代价仅为 $c_i$。

   我们需要取两种情况的最小值：
   [
   ans[i] = \min\left( \sum_{j \in \text{子结点}} ans[j],\quad c_i \right)
   ]

这样，最终答案就是 $ans[1]$，即整棵树满足条件的最小代价。

自底向上递推

由于输入保证 $f_i<i$，即父结点编号一定小于子结点编号。因此，如果我们从 $n$ 到 $1$ 倒序处理，当处理到结点 $i$ 时，它的所有子结点（编号都大于 $i$）一定已经处理完毕。我们可以直接利用已经算出的子结点答案来更新当前结点。

算法步骤：

• 用一个数组 cnt 记录每个结点的子结点数量，用于判断叶结点。
• 倒序遍历 $i = n \dots 1$：
  • 如果 cnt[i] == 0，将 $ans[i]$ 初始化为 $c_i$。
  • 随后执行 $ans[i] = \min(ans[i],\ c_i)$。此时非叶结点的 $ans[i]$ 已经在上层循环中被所有子结点的答案累加，因此它表示的就是子结点答案之和。
  • 将 $ans[i]$ 累加到父结点 $f[i]$ 的答案中，即 $ans[f[i]] \mathrel{+}= ans[i]$。
• 最后 $ans[1]$ 即为所求。

参考代码

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4
5const int N = 1e5 + 5;
6int n;
7int f[N], c[N], cnt[N];
8long long ans[N];
9
10int main() {
11    scanf("%d", &n);
12    for (int i = 2; i <= n; i++) {
13        scanf("%d", &f[i]);
14        cnt[f[i]]++;          // 统计子结点数量
15    }
16    for (int i = 1; i <= n; i++)
17        scanf("%d", &c[i]);
18    
19    for (int i = n; i >= 1; i--) {
20        if (cnt[i] == 0)      // 叶子结点
21            ans[i] = c[i];
22        ans[i] = min(ans[i], 1ll * c[i]);   // 与当前结点染色比较
23        ans[f[i]] += ans[i];  // 将最优代价传递给父结点
24    }
25    printf("%lld\n", ans[1]);
26    return 0;
27}

代码解释

• cnt[f[i]]++：在建树的同时统计每个结点的度数（子结点个数）。
• ans 数组使用 long long，因为 $c_i \le 10^9$，多个结点累加可能超过 int 范围。
• 倒序循环中：
  • 对叶结点，ans[i] 原本为 $0$，先赋值为 $c_i$，再和 $c_i$ 取 $\min$，结果不变。
  • 对非叶结点，此前子结点已经把各自的 ans 加到了 ans[i] 上。此时 ans[i] 已经是子结点答案之和。用 min 与 $c_i$ 比较，如果直接染 $i$ 更优，则更新。
  • ans[f[i]] += ans[i]：无论叶或非叶，都将当前结点的最优代价累加到其父结点。注意 $f[1]$ 未被赋值，默认为 $0$，ans[0] 的增加不影响最终输出。
• 最终 ans[1] 存储的正是整棵树的最小染色代价。

时间复杂度

• 预处理父子关系与代价：$O(n)$。
• 倒序循环一次：$O(n)$。
• 总时间复杂度：$O(n)$，空间复杂度 $O(n)$，可以轻松应对 $n \le 10^5$ 的数据规模。

总结

本题充分利用了树形 DP 的思想，将“覆盖路径”的条件转化为对子树最优解的定义，并通过自底向上的递推高效求解。输入顺序的特殊性（父结点编号小于子结点编号）使得我们无需显式建树或递归，即可在线性时间内解决问题。这是树形 DP 与拓扑顺序结合的一个经典案例。