ARC078D Mole and Abandoned Mine

题意：给一个 个点 条边的无向连通简单图，边有边权。

要求割掉若干条边，使 到 只有一条简单路径，问割掉的边权和最小是多少。

，时限 。

---

取反后可以转化为：保留一个边集使 到 只有一条简单路径，且边权和最大。

观察符合题意的图会长什么样，如下图：

会有很多子图挂在 的那条唯一的简单路径上，挂在两个不同点上的子图不能连通（如图中蓝边），否则不合法。

考虑状压 ，每次向链上加入一个点以及其挂着的子图。

记 表示已经考虑了集合 内的点，链的末尾为 的最优解。

记 为 之间的边权（若边不存在则为 ）， 为集合 内部的边权和。

则有转移：

分别对应“将链延长”与“挂一个子图在当前端点上”。

复杂度 。