题目内容

某公司有 $n$ 名员工，编号 $1$ 到 $n$，其中员工 $1$ 是首席执行官（CEO）。对于任意员工 $u$（$2 \le u \le n$），存在唯一的直接上级 $p_u$，上下级关系构成一个以 CEO 为根的连通无环层级结构（即树）。员工 $u$ 拥有绩效奖金 $a_u$。

现需组建一个特别项目组，恰好从公司中挑选 $k$ 名互不相同的员工。为保证团队扁平化，要求任意两名入选员工之间不存在管辖关系：若从 CEO 到员工 $y$ 的上下级路径（沿着直接上级关系从 CEO 走到 $y$ 所经过的结点序列）经过了员工 $x$，则称 $x$ 管辖 $y$。所选集合中不得有任何人管辖另一个人。

定义 $f(k)$ 为：在所有满足上述条件且恰好含有 $k$ 名员工的挑选方案中，所选员工绩效奖金总和的最大值。若没有任何一种合法的挑选方案，则 $f(k)=-1$。

请你对 $k=1,2,\dots,n$ 分别求出 $f(k)$。

约束：

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写