简答题 偏难
#16972

路径覆盖 时间限制 :3.0 s 内存限制 :512.0 MB 题目描述 给定一棵有 n 个结点的有根树 T ,结点依次以 1 , 2, . , n 编号 ,根…

路径覆盖

时间限制:3.0 s

内存限制:512.0 MB

题目描述

给定一棵有 n 个结点的有根树 T ,结点依次以 1 , 2, . , n 编号 ,根结点编号为 1 。方便起见 ,编号为 i 的结点称为结点 i。

初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结

点。将结点 i 染为黑色需要代价 c,你需要在满足以上条件的情况下,最小化染色代价之和。

叶子是指 T 中没有子结点的结点。

 输入格式

第一行,一个正整数 n,表示结点数量。

输出格式

一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。

输入样例 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

数据范围

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:python;toolbar:false">getint = lambda: map(int, input().split()) getints = lambda: list(getint()) # 获取节点数 n = int(input()) # 各个节点的根节点 f = [0, 0] + getints() # 各个节点涂黑的成本 c = [0] + getints() # cnt[i]表示节点i有多少子节点 cnt = [0] * (n + 1) # ans[i]表示以节点i为根节点的子树,需要多少成本才能让所有叶子结点到根节点都有涂黑的节点 ans = [0] * (n + 1) # 统计一个节点有多少子节点 for i in range(2, n + 1): cnt[f[i]] += 1 # 遍历每一个节点,因为一个节点的父节点编号肯定这个节点,所以大编号的一定更深 for i in range(n, 0, -1): # 如果一个节点没有子节点,那么显然ans[i]=c[i]就是把自己涂黑 if cnt[i] == 0: ans[i] = c[i] # 一个节点当前已经找到的答案等于 ans[i] = min(ans[i], c[i]) ans[f[i]] += ans[i] print(ans[1])</pre>
这道题暂未补解析。