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

问题描述

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

问题解答

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

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

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

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