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)​​​​ 个，维护树上前缀异或和即可得到每个树上简单环的异或和，扔进线性基即可。

#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;
}