题面

给定一张有 $n$ 个点和 $m$ 条边的无向图 $G$ ，同时进行 $q$ 次询问。每次询问包含三个点 $u, v, w$ ，试问同时从 $v, w$ 出发到达 $u$ 是否存在两条互相不包含相同边的路径。

数据范围：

$1 \le n \le 10^5$

$0 \le m \le 2 \times 10^5$

$1 \le q \le 10^5$

所有测试点满足 $\sum n \le 5 \times 10^5, \sum m \le 10^6$ 。

分析

我们首先注意到，题目本质上等价于询问从 $v$ 出发到达 $w$ 是否存在一条经过 $u$ 并且不包含重复边的路径。

我们不妨先考虑一个简单一点的情况。我们假设题目中给定的图是一棵树，那么问题就变成了在一棵树上从 $v$ 到 $w$ 的最短路径（树中两点间不包含重边的路径就是最短路径）是否一定经过 $u$ 。

对于这个问题，我们很容易想到可以借助 LCA（最近公共祖先）来解决。我们可以对于 $v, w, u$ 在树中的深度 $depth$ 分如下几种情况讨论：

如果 $depth(u) < \min\{depth(v), depth(w)\}$ ，也就是从 $v, w$ 出发都要往上（树根方向）行走才可能到达 $u$ ，那么当且仅当 $lca(v, w) = u$ 时我们才能保证 $v, w$ 之间路径经过 $u$ ；
如果 $depth(u) > \max\{depth(v), depth(w)\}$ ，显然两点间路径是不可能经过 $u$ 的；
在剩余的情况下， $depth(u)$ 是介于 $depth(v)$ 和 $depth(w)$ 之间的。为了方便讨论，我们不妨假设 $depth(v) < depth(w)$ ，也就是 $v$ 需要向下走才能到 $u$ ，而 $w$ 要向上走才能到 $u$ 。在这种情况下，当且仅当 $lca(w, u) = u$ 时才能保证 $v, w$ 之间路径经过 $u$ 。

我们对上述三种情况做一个综合，也就是当且仅当 $lca(v, w) = u$ ，或者 $lca(w, u)$ 和 $lca(v, u)$ 中有且仅有一者等于 $u$ 时，树上 $v, w$ 两点之间的路径一定经过 $u$ 。

那么我们进一步将这个问题复杂化：如果给定的是一个森林，我们该如何解决？

其实也很简单，我们只需要再额外建立一棵超级树根 $r$ ，然后将森林中的每一棵树的树根都连向 $r$ 即可。如果出现两点的 $lca$ 等于 $r$ ，便说明这两点间不连通。这个过程可以借助并查集实现。

由此一来，我们就把森林上的问题转变为上文所述的树上问题了。

最后我们回到原题目，原题目中给的是一张图。我们有没有办法将图上问题转化为森林上的问题呢？

我们首先注意到，如果从 $v, w$ 同时出发到达 $u$ 都要经过一条相同的边，那么这条边一定是原图中的一条割边（桥）。换句话说，如果 $u, v, w$ 都在同一个边双连通分量 (e-DCC) 中的话，那么一定是存在两条互相没有重边且分别从 $v, w$ 到达 $u$ 的路径的。

对于三者不都在同一个边双连通分量中的情况，由于边双连通分量保证了其中任意两点间不重边的路径不唯一，所以只要 $v, w$ 能够不走相同边各自到达 $u$ 所在双连通分量中的任意一个点（哪怕这两个点是同一个点），在这个双连通分量中我们一定能找到两条不含相同边的路径使它们各自到达 $u$ 点。

缩点是最常见的将图上问题转化为树上问题的手段，因此我们可以用 Tarjan 算法先将原图上的所有边双连通分量缩成一个点，从而得到一个森林。再在这个森林上进行上文所述的判断就解决了这道题。

不过我们需要注意的是，缩点之后 $u, v, w$ 三个点不一定分布在三个不同的边双连通分量之中。对于这种情况，我们不难发现，只要这三个点互相连通，只要 $u, v$ 或者 $u, w$ 在同一边双连通分量中的话就一定是可以的。

我的解法需要用到 Tarjan (e-DCC)， LCA (树上倍增) 以及并查集。因此实现起来还是有一点点复杂的…… QAQ。

好气啊…… QAQ 从来没做过这种题的我在比赛中好不容易想到了这种解法，没想到最后有点细节写挂了狂 WA……在队友的帮助下发现后最后一刻刚改完比赛就恰好结束了…… 题目被传上题库后立马交了一发没想到竟然 1A 了…… 呜呜呜，又把队友的名额演没了。

不过这也算是我的第一篇完全独立自主写出来的题解呢~