P4151 - 最大XOR和路径 题解

考虑 $1\to n$​ 所有路径的边权异或和集合长什么样。定义两个边集的异或和为恰好出现在一个边集里的边的集合。首先知道边集一般不考虑简单环还是复杂环。复杂环、甚至是若干个不连通的环的集合，都可以由简单环集合线性表出。所有这样的满足每个点度数为偶的边集的集合，不难发现它对唯一的线性运算——异或封闭，所以是一个线性空间，元素为边集（其实也可以看成 01 向量啦）。 然后不难想到，$1\to n$ 的所有路径，其实就是先随便选一条，然后把上述线性空间里所有元素依次异或上去，得到所有路径。证明一下？一个边集是 $1\to n$​ 的路径其实当且仅当除 $1,n$ 为奇度以外，其它点都是偶度。那得到的这些边集是 $1\to n$ 路径其实就显然了，反过来只有这些是 $1\to n$ 路径是不是也显然啊（）。所以 $1\to n$ 的所有路径的边集其实就是一个线性空间异或上一个平移量，线性空间是所有简单环的生成空间，平移量是 $1\to n$ 任意一条路径。 但是即使找到了这个生成空间的一个基的一个超集——简单环集合，但这还是太多了，简单环哪里能枚举的过来？考虑任意一棵生成树，一个结论是：非树边对应简单环的集合是基的一个超集。感觉上很对吧，就感觉生成树上的简单环能线性表出所有简单环，找不到反例对吧。但我们需要一个严谨的证明：每条非树边最多出现在一个树上简单环里对吧。对每个简单环的异或和，把所有非树边去掉，去掉的方式是异或上对应树上简单环，显然是可实现的。最后依然得到另一个简单环的异或和，而它没有非树边，只有树边，想仅由树边组成至少一个环是不可能的，所以必须是空集，那么原集合能被树上简单环线性表出就被证明了。 而且最后不需要真的求这个元素为边集的线性空间的一组基。最后要求的其实是，这个线性空间里每个元素的异或和得到的新线性空间（对边集取边权异或和显然是个线性变换）的一组基。那显然树上简单环的异或和集合是新线性空间的一组基，平移量也取对应异或和。可以选 dfs 树（其实其它生成树也可以，dfs 树只有返祖边比较舒服），树上简单环是 $\mathrm O(m-n)$​​​​ 个，维护树上前缀异或和即可得到每个树上简单环的异或和，扔进线性基即可。 ```cpp #include<bits/stdc++.h> using namespace std; #define int long long #define X first #define Y second #define pb push_back #define mp make_pair const int N=1000010; int n,m; vector<pair<int,int> > nei[N]; bool vis[N]; int xsm[N]; int b[N]; void insert(int x){ for(int i=60;~i;i--)if(x>>i&1) if(b[i])x^=b[i]; else{b[i]=x;break;} } void dfs(int x=1,int fa=0){ vis[x]=true; for(int i=0;i<nei[x].size();i++){ int y=nei[x][i].X,v=nei[x][i].Y; if(y==fa){fa=-1;continue;} if(!vis[y])xsm[y]=xsm[x]^v,dfs(y,x); else insert(xsm[x]^xsm[y]^v); } } signed main(){ cin>>n>>m; while(m--){ int x,y,v; scanf("%lld%lld%lld",&x,&y,&v); nei[x].pb(mp(y,v)),nei[y].pb(mp(x,v)); } dfs(); int res=xsm[n]; for(int i=60;~i;i--)if(res>>i&1)res^=b[i]; cout<<res; return 0; } ```