题解：P6658 边三连通分量

沉石鱼惊旋 · 2025-10-16 20:32:57 · 题解

边三的定义就是：存在三条从 u 出发到达 v 的，相互没有公共边的路径。

我们把这个条件转化一下，考虑切边等价：两个点 u,v 不在一个边三中，就是存在两条边 e_1,e_2，割掉他俩之后，u,v 不连通。

我们考虑怎么刻画这个割掉之后不连通的条件。

取出原图的一棵 DFS 树，对于非树边随机赋权，给树边同时异或上把他覆盖的非树边边权。

分类讨论一下我们割的边的类型：

• 两条非树边：显然不可能，因为树边已经让整张图都连通了。
• 一条树边，一条非树边：需要满足，该树边仅被这条非树边覆盖。也就是两条边边权一样。
• 两条树边：如果两条边不成祖先后代链关系，除了没有非树边覆盖他俩的情况（存在树边权为 0），都不可能。而成祖先后代链关系的情况，就是不存在一条边，从中间的那一块连出去了。刻画到赋权之后，就是两条边边权也要一样。

所以其实就是，把相同边权的还有 0 边权的割掉。

考虑刻画这个割的过程，我们对点再做一次 XOR Hash 就可以刻画出来点的等价类了。

实现的时候，边权为 0 的树边还有存在树边与非树边边权为 0 的割掉是容易实现的，第三种两条树边的情况，我们维护一下上次出现这个边权是在哪一条边，然后分别给两个子树打上 XOR Hash 的 tag 即可。

最后再做一次 DFS 下放对点做的 XOR Hash 的标记。只需要两次 DFS 即可实现，最后的 XOR Hash 结果一样的点就是在一个边三里。