pjudge 题解虽然写了，但可能是 bot 写的，写的很不清楚。
根据经典做法，搜出一棵 dfs 树，对非树边赋随机权值，树边权值为跨过它的所有非树边的权值 xor。
那割三条边能割开的条件就是：选三条边的一个子集，这个子集中的边权 xor 为 0。
也就是存在 \(w_i = 0\) 或 \(w_i \oplus w_j = 0\) 或 \(w_i \oplus w_j \oplus w_k = 0\)。
考虑对图进行一些预处理，判掉一些简单情况。
首先判掉割边：对于一条割边，先计算割了它的答案，再把两个端点用并查集缩起来，表示以后再也不会割这条边。
处理完了图上不会有 \(w_i = 0\) 的边（也就是割边）。
接下来有一步炫酷操作。
先计算割两条边（再加随意一条边）就能把图割开的情况，也就是 \(w_i \oplus w_j = 0\) 的情况。只需要找到所有权值相等的边进行计算。
接下来的限制就是只有砍三条边，也就是 \(w_i \oplus w_j \oplus w_k = 0\) 的情况。
由于没有 \(w_i = 0\)，那么 \(w_i,w_j,w_k\) 都是不同的，也就是同一权值的边只会割一条。
观察到相同权值的边割哪条效果都是一样的，可以对图进行如下处理：
给每条边加上“长度” \(l_i\)，表示割这条边答案乘上几（也就是说砍三条边的话答案加上 \(l_i\times l_j\times l_k\)）。把同一颜色的边中，选一条将长度设为边的数量，其他的长度设为 0。容易发现不改变答案。
对于长度为 0 的边，可以直接并查集把两个端点缩起来。
这样缩完以后，图上没有权值相同的边，并且因此图上没有度数 \(\le 2\) 的点，这对后面操作的复杂度证明有用。
接下来分类讨论砍三条边的情况。
零、三条非树边
由于树边一定使图联通，所以不可能。
一、一条树边，两条非树边
枚举这条树边，看看是否恰有两条非树边跨过这条树边。这部分容易统计。
二、两条树边，一条非树边
退役了。
三、三条树边
此时的方案中，非树边一定不会被割。
所以可以将非树边两端的端点用并查集并起来，得到一张新图，在新图上继续做。
由于图中每个点的度数至少为 \(3\)，因此 \(|E| \geq \frac{3}{2} |V|\)，故被缩掉的边数至少为 \(|E| - |V| + 1 \ge \frac{1}{2}|V|\)。
于是缩的轮数只有 \(\log m\) 轮。在每轮中都统计前两种情况即可。
标签：drogi,树边,查集,PA,2020,权值,三条,oplus,非树边 From： https://www.cnblogs.com/Rainbowsjy/p/17305030.html