c++ - 一道应不应该用树状dp的题

Question

有一颗n节点的最多三叉的树，最多有1000个节点。
现在我要取其中的m个节点，m不超过100
想要的是取得所有点和与所有点相邻的点的和要最大
有点没有思路啊，求解。

Answer 1

就用树型 DP 啊，然后最多三叉，所以可以直接把当前节点和儿子节点是否加到答案里压缩起来。

状态就是记 f(i,j,S) 表示在子树 i 中选中了 j 个节点（不包括节点 i），加到答案里的节点集合为 S，子数的贡献。

转移就是分 i 被选择和不被选择向 i 的父亲转移，这里还要枚举还有枚举父亲的 j、S。

复杂度不会超过 O(n^2*8^2)。