g6-07512. 森林依赖选择 · 林老师的题库

题目描述

给定一片森林（若干棵有根树），共 $n$ 个结点，结点 $i$ 有权值 $w_{i}$ （可为负）。

选择若干结点，满足：若结点 $i$ 被选且它不是所在树的根，则它的父亲也必须被选；对每棵树，要么一个结点都不选，要么必须选它的根。所选结点数不超过 $m$ 。

求所选结点权值和的最大值。允许一个结点都不选，此时权值和为 $0$ 。

第一行两个整数 $n$ 与 $m$ 。

第二行 $n$ 个整数 $w_{1}, w_{2}, \dots, w_{n}$ 。

第三行 $n$ 个整数 $f_{1}, f_{2}, \dots, f_{n}$ ： $f_{i} = 0$ 表示 $i$ 是所在树的根，否则 $f_{i}$ 是 $i$ 的父亲（保证 $f_{i} < i$ ）。

一行一个整数。

输入：

4 3
5 -1 4 2
0 0 1 0

输出：

森林： $1$ （带儿子 $3$ ）与 $4$ 两棵树， $2$ 单独成树。选 ${1, 3}$ 得 $5 + 4 = 9$ ，共 $2$ 个结点。