题目链接

传送门

一句话题意

你有一张$N$个点$M$条边的无向图,每条边上都有权值,现在请你求出来一条路径,使得这条路径上所有边权的异或和最大。

题解

这题显然我们需要找的路径是一条$1->n$的简单路径(不经过环的那种)加上很多个环
Q:假如说我现在看到了一个环,但是它离我现在这条路径很远怎么办,我要不要走
A:当然是要看看那个环的权值怎么样了
Q:那这样的话我从现在的位置过去会不会导致权值变小呢
A:显然不会,走完这个环之后你可以选择原路返回,这样的话你得到的贡献只有那个环上面的,一来一回两条路径全都抵消掉了,没有任何影响
Q:这些我懂了,但是你说还要找一条简单的路径,呢么这条简单的路径有没有什么选择的标准呢
A:没有,原因如下:
假设存在一条更优的路径从$1$到$n$,那么这条路径与我们原来的路径构成了一个环,也就会被纳入线性基中,也会被计算贡献,假如这个环会被经过,那么最后的情况相当于是走了两遍原来选取的路径,抵消之后走了一次这个最优路径,所以我们无论选取的是哪条路径作为ans初值,都可以通过与更优情况构成环,然后得到一样的结果。这一证明可以拓展到路径上的任意点的路径选取
Q:说的很有道理,你写写看好不好
A:好的


Q:请问你为什么WA了呢,接着调好不好呢


Q:你到底会不会,接着调成不?

A:我会了

代码