双连通分量 – Kalorona

BZOJ3590:「SNOI2013」Quare – 题解

我操这个题是真的有意思（~~做完后索然无味~~）。

肯定这个题状压 DP 没跑的，所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难，我们需要思考一个归纳的方式来构造一个双连通图。

乍一看没办法维护图的最大点权和，但是注意到没有删边操作，且注意到一个双连通分量可以被缩点，所以我们可以用 LCT 来维护双连通分量。

考虑开两个并查集，一个是双连通分量的并查集，标号为 \(0\)；另外一个是维护连通性的并查集，标号为 \(1\)。