AT_arc078_d
\(n \le 15\)
首先，我们来尝试是刻画一下这张图长啥样？（如下图）一定是一条路径，路径上每个点挂着一个连通块，还有一些散块。
可以发现，这个结构要求最少删多少不太好算，不如算最多留下多少。
令 \(f(S, x)\) 表示 \(1\) 到 \(N\) 的路径已经经过了 \(S\)，路径上最后一个点是 \(x\) 的方案数。如果枚举下一个点 \(y\) 以及那个连通块，复杂度陡增。
不难发现那个连通块其实和 \(x\) 没啥关系，于是可以把这个分成两步转移：
-
\(f(S, x) \rightarrow f(S \cup \{y\}, y)\)。
-
\(f(S, x) \rightarrow f(S \cup T, x)\)。
加的边权之和预处理一下即可。至于对于一个 \(x\) 多次执行第二种操作，没有关系，因为肯定不如一次性加入更优。
时间复杂度：\(O(n3^n)\)。