BZOJ2959:长跑 – 题解

主要思路

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

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

Continue reading →