还记得 OI 时期有一道典的不能再典的题目：给一张图，求一条从 $s$ 到 $t$ 的最大异或和的路径。

一个很典的结论是：跑一棵生成树，然后把这棵生成树上的环全部拿下来做个线性基，然后用任意一条 $s\to t$ 的路径丢进线性基里求最大值。

之前一直不知道怎么证明。

现在来证明一手：

不妨假设图中只有一个联通图。

可以发现，答案路径和随便一条路径的对称差满足每个点的度数都为 $0$ ，我们不妨把所有满足所有点度数为 $0$ 的边集集中到一个集合 $S$ 。

显然，不仅路径的对称差属于 $S$ ，$S$ 的任意一个元素都显然可以称为路径的对称差，因此，任意一条路径的异或和，和答案的异或值，可以且仅可以是 $S$ 中某个元素的异或值。

然后在这个集合上定义一种类似异或的运算：对应两个集合 $X,Y$ ，这种运算的返回结果为：$(X\cup Y)\setminus(X\cap Y)$ ，下面直接称这种运算为异或。

显然这个运算是封闭的（即结果还在这个集合内），显然这个结构能够像线性基一样定义基（把存在或不存在看成 $0/1$ 就可以直接看成线性基了），如果能够证明基的大小是 $m-(n-1)$ ，那么这个问题就解决了。

考虑生成树用到的边集 $E_1$ ，那么显然 $E\setminus E_1$ 中的每个元素都会生成一个环，这下环构成的集合我们称为 $S’$ ，显然 $S’\subset S$ ，且 $S’$ 线性无关，现在我们证明这个组合能够表示出 $S$ 就行了。

对于任意一个 $S$ 的元素 $L$，对于 $L$ 中非 $E_1$ 的元素，我们将他们拉出来异或，得到元素 $L’$ ，显然 $L,L’$ 在 $E\setminus E_1$ 的部分是相同的，而在 $E_1$ 的部分，显然也能根据树的结构以及度数都为 $0$ 这一性质证明是相同的，这样，就构造性的证明了 $L’=L$ ，因此 $S’$ 就是 $S$ 的一组基。

证毕。

说起来，现在用异或的角度观察图的结构发现，图的结构其实和向量空间很像，不过只有一个运算。

同时从拟阵的角度来看，图拟阵和有限的向量空间都是拟阵。

太神奇了，可惜碍于我浅薄的知识面，无法看见更加深层次的联系，实在可惜。