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

Question

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

Answer 1

ツリー DP を使用するだけで、最大 3 つのフォークに対応できるため、現在のノードと子ノードを回答に直接追加して圧縮できます。

状態は f(i,j,S) として記録されます。これは、サブツリー i で j 個のノード (ノード i を除く) が選択されることを意味し、答えに追加されるノードのセットは S であり、サブツリーの寄与度になります。 Sです。

転送とは、i が選択されているかどうかにかかわらず、i の父親に転送することです。ここでも、父親の j と S を列挙する必要があります。

複雑さは O(n^2*8^2) を超えません。