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

Question

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

Answer 1

Just use tree DP, and it can be up to three forks, so you can directly add the current node and child nodes to the answer and compress it.

The state is recorded as f(i,j,S), which means that j nodes (excluding node i) are selected in subtree i. The set of nodes added to the answer is S, and the contribution of the subtree is S.

Transfer means transferring i to i's father if i is selected or not. Here we also need to enumerate and enumerate the father's j and S.

The complexity will not exceed O(n^2*8^2).