建站实战干货

看到这道题如果做过 P4151 [WC2011] 最大XOR和路径 就很容易想到这个询问的本质 —— 在图上走若干个环使其经过边权异或和最大。

对于任意环，从 \(1\) 走到环上任意点 \(u\) 走一圈后再走回 \(1\)，发现 \(1\to u\) 上的边都走了两次异或和为 \(0\)，所以剩下的就是环上的边权异或和。

考虑找到每个环。实际上只需要找到一棵 dfs 树，对于非树边 \((u,v,w)\) 将 \(dis_u\bigoplus dis_v \bigoplus w\) 加入即可。

对于任意环无非是从 \(u\) 走若干非树边到 \(v\)，再从 \(u,v\) 分别经过若干返祖边走到 \(w,p\) 且 \(w,p\) 能通过非树边到达或是走到根。

维护可删除线性基，