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)。