4732: 【GESP2512六级】路径覆盖

/*
 * 试题名称：路径覆盖
 * 题目大意：给定一棵根为1的有根树，叶子到根的每一条路径上至少存在一个黑色结点。
 * 将结点i染黑代价c[i]，求满足条件的总最小染色代价。
 * 数据范围：n ≤ 1e5，父结点f[i] < i，可逆序遍历代替DFS后序遍历
 */
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1e5 + 5;
int n;
int f[N];      // f[i]：i的父节点编号
int c[N];      // c[i]：把i染黑的代价
int cnt[N];    // cnt[ u ]：u的子节点数量，cnt[ u ]==0代表u是叶子
long long ans[N]; // ans[i]：以i为根的子树全部满足条件的最小总代价

int main()
{
    scanf("%d", &n);
    // 读入2~n每个点的父节点，统计每个父节点的子节点计数
    for (int i = 2; i <= n; i++)
    {
        scanf("%d", &f[i]);
        cnt[f[i]]++;
    }
    // 读入每个结点染色代价
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);

    /*
     * 逆序循环 i从n到1，因为父节点编号一定小于子节点
     * 保证处理父i的时候，i的所有子节点已经全部处理完成（等价后序遍历）
     */
    for (int i = n; i >= 1; i--)
    {
        // 如果i是叶子结点：叶子本身这条路径必须有黑点，只能选把自己染黑
        if (cnt[i] == 0)
            ans[i] = c[i];

        // 决策：当前结点i可以选择染黑，代价c[i]
        ans[i] = min(ans[i], 1ll * c[i]);

        // 将i的最小代价贡献加到父节点f[i]上，父节点汇总所有子树的最小代价
        ans[f[i]] += ans[i];
    }
    // 根结点1的子树就是整棵树，输出根节点的答案
    printf("%lld\n", ans[1]);
    return 0;
}