题解 T93222 【生成树】

传送门

30%的题解：

• 是一棵树，所以只要枚举根，然后计算代价即可

100%的题解：

• $vals[S]$表示集合$S$的权值和

• 设计状态$F[S][h]$, 表示现在已经选择了的点的集合是$S$，$h$表示当前深度

• 枚举S的补集的子集$S_2$，只要满足$S_2$中每个点都有和$S$集合中某个点相连的话，就可以转移到$F[S|S_2][h+1]$,转移费用是$(h+1)*vals[S_2]$

• 时间复杂度$O（n \times 3n）$

• 这题修改自NOIP2017宝藏