权值和最大的k条叶子链 | 星码StarryCoding | 算法竞赛新手村 | ACM、OI、蓝桥杯、天梯赛、CCF、ACM-ICPC、大学生信息学竞赛

P360 权值和最大的k条叶子链

时间限制 400 ms	空间限制 256 MB	难度
提交次数 25	通过次数 7	未做过本题

题目描述

给定一个以 $1$ 为根，由 $n$ 点构成的树（编号从 $1$ 到 $n$ ），节点有权值 $a_i$ ，现在你最多选择 $k$ 个叶子节点，并将从其到根上这条链打上标记。

请问最后所有被标记的节点的权值之和，最大是多少？

第一行一个整数 $T(1 \le T \le 100)$ ，表示样例数量。

对于每组样例：

第一行两个整数 $n, k(2 \le \sum n, k \le 2 \times 10^5)$ 。

第二行 $n$ 个整数表示 $a_i(1 \le a_i \le 10^9)$ 。

第三行 $n-1$ 个整数表示 $2 \sim n$ 节点的父亲节点编号 $fa_i$ 。

对于每组样例，一行一个整数表示答案。

text 复制代码

text 复制代码

快捷菜单

在线运行

语言：

登录后可在线运行与提交。