有一颗n节点的最多三叉的树，最多有1000个节点。
现在我要取其中的m个节点，m不超过100
想要的是取得所有点和与所有点相邻的点的和要最大
有点没有思路啊，求解。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
1
827
![ThinkPHP5快速开发企业站点[全程实录]](https://img.php.cn/upload/course/000/000/068/6253d918a3ce7278.png)
收藏
就用树型 DP 啊，然后最多三叉，所以可以直接把当前节点和儿子节点是否加到答案里压缩起来。
状态就是记 f(i,j,S) 表示在子树 i 中选中了 j 个节点（不包括节点 i），加到答案里的节点集合为 S，子数的贡献。
转移就是分 i 被选择和不被选择向 i 的父亲转移，这里还要枚举还有枚举父亲的 j、S。
复杂度不会超过 O(n^2*8^2)。