题解：AT_arc193_b [ARC193B] Broken Wheel

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

首先不考虑 $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)$。