解题思路

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

于是可做树形背包 DP：

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

P3589.第3题-祖先节点

1000ms

Difficulty: 8

所属公司 : 美团

算法与标签>动态规划

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

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

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

【名词解释】

祖先节点：在一棵以 $u$ 为根的树中，若点 $x$ 在 $u$ 到 $v$ 的简单路径上，且 $x≠v$ 则称 $x$ 是 $v$ 的祖先节点。根节点没有祖先节点。

每个测试文件均包含多组测试数据，第一行输入一个整数 $T(1≦T≦1000)$ 代表数据组数，每组测试数据描述如下：

第一行输入一个正整数 $n(1≦n≦5000)$ ，代表树中的节点数量。

第二行输入 $n$ 个正整数 $a_1,a_2,...,a_n(1≦a_i≦10^9)$ 表示每个节点的点权。

接下来 $n-1$ 行，第 $i$ 行插人两个正整数 $u_i,v_i(1≦u_i,v_i≦n)$ ，表示树上一条从节点 $u_i$ 到 $v_i$ 的边。输入保证是一棵合法的树。

除此之外，保证单个测试文件的 $n$ 之和不超过 $5000$ 。

输出一行 $n$ 个整数，其中第 $i$ 个整数代表 $f(i)$ 。

输入

输出

114514
5 6 9 -1

输入

预期输出（选填）