题解：AT_arc193_b [ARC193B] Broken Wheel

Implicit · 2025-02-25 16:16:07 · 题解

通过观察发现，答案恰好等于原图的生成森林数量。那么只需要计数原图的生成森林。

首先不考虑 0-(n-1) 这条边，对 0\dots n-1 这条链进行 DP。令 dp_{i,0/1,0/1,0/1} 表示考虑到第 i 个点、当前点所处的连通块是 / 否包含点 n、点 0 所处的连通块是 / 否包含点 n、点 n-1 所处的连通块是 / 否包含点 n，转移平凡。之后对于 0,n-1 不全和点 n 连通的情况额外计算连边 0-(n-1) 的情况即可。

时间复杂度 \Theta(n)。