G6019 [GESP202512 六级] 路径覆盖 题解

知识点：树形动态规划、最小费用、后序遍历。

解题思路

令dp[u]为覆盖该子树全部叶到u路径的最小染黑费用。叶节点取c[u]；内部节点取min(c[u],所有孩子dp之和)。

为什么正确

要么染黑u，整棵子树所有路径立即被覆盖；要么不染u，每个孩子子树都必须独立覆盖，两个选择完整且互斥。

易错点

输入保证父编号更小，所以倒序编号就是可用后序；根也允许染黑。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>p(n+1),child(n+1);
    for(int i=2;i<=n;i++) {
        cin>>p[i];
        child[p[i]]++;
    }
    vector<long long>c(n+1),dp(n+1);
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=n;i>=1;i--) {
        if(child[i])dp[i]=min(c[i],dp[i]);
        else dp[i]=c[i];
        if(i>1)dp[p[i]]+=dp[i];
    }
    cout<<dp[1];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。