1000ms

Difficulty: 8

所属公司 : 美团

时间 :2025年9月6日-算法岗

算法与标签>动态规划

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

关键观察

在以 $u$ 为根的子树中，若选择了结点 $u$ ，则它的整个子树都不能再选任何结点；若不选 $u$ ，则可以在它的各个子树中独立选择，且不同子树之间互不影响（不同子树的结点不可能互为祖先）。

于是可做树形背包 DP：

记 $dp[u][k]$ ：在结点 $u$ 的子树中，选出恰好 $k$ 个两两不成祖孙关系的点时的最大权值和（不可行记为 $-\infty$ ），并规定 $dp[u][0]=0$ 。

题目内容

给定一棵树，根节点为 $1$ ，其中第 $u$ 个节点有点权 $a_u$ ，定义 $f(k)$ 为：

选择树上 $k$ 个互不相同的节点。你需要保证这 $k$ 个节点两两不成祖先-子孙关系。 $f(k)$ 为在所有可能的选择方案里最大的点权和。如果不存在任何一种合法的选择方案，则 $f(k)=-1$ 。

计算 $f(1),f(2),…,f(n)$ 。