题意：n个点的带边权完全图，求出最小生成树，其权定义为
w(T)=\sum_{1\leq u<v\leq n} dis(u,v)
n\leq 17
sol：
假设生成树为 T , 其中某条边 <u,v> 的权值为 w ; 两侧子树大小分别为 x, y 那么该边对全局的贡献为
w\times x\times y
对于一个已经连通的集合 S ，我们指定一个根 i 使得其他点与该集合的连边强制连向 i
考虑状压dp合并两个子树，定义状态 f_{i,S} 为以点 i 为根的子树打通了集合 S 的最小代价，转移为
f_{i,S}=\min_{j\in T\subset S, i \in S-T}\{f_{j,T}+f_{i,S- T}+w(i,j)\times\vert T\vert \times (n-\vert T\vert )\}
可以保证当前边的贡献在整个dp过程中被计算仅一次.
复杂度 O(n^23^n)，考虑优化。
发现 f_{j,T}+w(i,j)\times\vert T\vert \times (n-\vert T\vert) 只和 i,j,T 有关
考虑定义 g_{u,T} 为对于 u 来说最小的 f_{v,T} ，即 g_{u,T}=\min_{v\in T}\{f_{v,T}+w(u,v)\times\vert T\vert\times(n-\vert T\vert)\} ，可在求出某个 \forall u,f_{u,S} 以后在O(n^2)时间之内处理出来\forall u, g_{u,S}，复杂度 O(2^n\times n^2) .
接着转移就变成了
f_{i,S}=\min_{T\subset S}\{f_{i,S- T}+g_{i,T}\}
一个虚假的优化: \forall i,j \in S, f_{S,i}=f_{S,j} 因为考虑的是全局贡献而不是集合连通的局部贡献。这个结论当且仅当 S 为全集的时候正确,此时局部贡献=全局贡献.