A22018. 路径覆盖
填空题
困难
知识点
题目描述
路径覆盖
题目描述
给定一棵有n个结点的有根树T，结点依次以1,2,....n编号，根结点编号为1。方便起见，编号为i的结点称为结点i。
初始时T中的结点均为白色。你需要将T中的若干个结点染为黑色，使得所有叶子到根的路径上至少有一个黑色结点。将结点i染为黑色需要代价ci，你需要在满足以上条件的情况下，最小化染色代价之和。
叶子是指T中没有子结点的结点。
输入格式
第一行，一个正整数n，表示结点数量。
第二行，n-1个正整数f2,f3，...,fn，其中f表示结点i的父结点的编号，保证fi<i。
第三行，n个正整数c1,c2,...,cn，其中Ci表示将结点i染为黑色所需的代价。
输出格式
一⾏，一个整数，表⽰在满⾜所有叶⼦到根的路径上⾄少有一个⿊⾊结点的前提下，染⾊代价之和的最⼩值。
样例
输入样例 1
4
1 2 3
5 6 2 3输出样例 1
2输入样例 2
7
1 1 2 2 3 3
64 16 15 4 3 2 1输出样例 2
10数据范围
对于40的测试点，保证2≤n≤16。
对于另外20的测试点，保证fi=i-1。
对于所有测试点，保证2≤n≤105，1≤ci≤109。
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
int main() {
scanf("%d", &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]);
for (int i = n; i >= 1; i--) {
if (cnt[i] == 0)
ans[i] = c[i];
ans[i] = min(ans[i], 1ll * c[i]);
ans[f[i]] += ans[i];
}
printf("%lld\n", ans[1]);
return 0;
}
上一题
下一题