简答题 偏难
#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

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 ≤10^5, 1 ≤ci ≤10^9

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; #include &lt;algorithm&gt; #include &lt;vector&gt; using namespace std; const int N = 1e5 + 5; int n; int f[N], c[N], cnt[N]; long long ans[N]; vector&lt;int&gt; son[N]; int main() {     scanf("%d", &amp;n);     for (int i = 2; i &lt;= n; i++) {         scanf("%d", &amp;f[i]);         son[f[i]].push_back(i);         cnt[f[i]]++;     }     for (int i = 1; i &lt;= n; i++)         scanf("%d", &amp;c[i]);     for (int i = n; i &gt;= 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>
这道题暂未补解析。