简答题
偏难
#19808
路径覆盖 题目描述 给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的…
路径覆盖
题目描述
给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。 叶子是指 T 中没有子结点的结点。
输入格式
第一行,一个正整数 n ,表示结点数量。 第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i 第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。
输出格式
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于 40% 的测试点,保证 2 ≤n ≤16
对于另外 20% 的测试点,保证 fi=i-1 对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
vector<int> son[N];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
son[f[i]].push_back(i);
cnt[f[i]]++;
}
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = n; i >= 1; i--) {
ans[i] = c[i];
long long sum = 0;
for (int v : son[i]) {
sum += ans[v];
}
ans[i] = min(ans[i], sum);
}
printf("%lld\n", ans[1]);
return 0;
}</pre>
这道题暂未补解析。