ABC318G Typical Path Problem

给定无向连通图，问是否存在一条从 \(A\) 到 \(C\) 经过 \(B\) 的简单路径。
\(n \le 3 \times 10^5\)。

怎么这个 G 这么简单我还没写完啊？怎么这个 G 这么简单我还没写完啊？怎么这个 G 这么简单我还没写完啊？怎么这个 G 这么简单我还没写完啊？怎么这个 G 这么简单我还没写完啊？怎么这个 G 这么简单我还没写完啊？

官方题解网络流，不知道怎么想的。

我们把图缩个点双，然后根据点双的性质，即同一个点双内部的一对点之间至少存在两条简单路径，发现 \(A\) 到 \(C\) 存在经过 \(B\) 的简单路径的充要条件是在缩点之后 \(B\) 所在的点双在点双树上 \(A\) 到 \(C\) 的路径上。那么直接大力建个圆方树然后在圆方树上跳 LCA 就行。

时间复杂度严格 \(\mathcal{O}\left(n + m\right)\)，貌似薄纱了官方题解。

代码 link。