好题
先把一条1~n的路径搞出来。
然后再找环，由于是无向连通图，所以必定能到达环，若该环没有和路径接触，环绕一圈原路返回的价值就是环的xor和，假如接触，相当于换了一部分连接的路径。
那么剩下的就是线性基的工作了。
回溯的时候不要恢复。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<map> using namespace std; typedef long long LL; int n,m; struct node { int x,y,next;LL d; }a[210000];int len,last[51000]; void ins(int x,int y,LL d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } LL ans;bool bk,v[51000]; void prdfs(int x) { if(x==n){bk=true;return ;} for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(v[y]==false) { ans^=a[k].d; v[y]=true; prdfs(y); if(bk==true)return ; /// v[y]=false; ans^=a[k].d; } } } LL s[51000]; LL plen,p[210000];map<LL,bool>mp; void dfs(int x,LL d) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(s[y]==-1) { s[y]=d^a[k].d; dfs(y,d^a[k].d); } else { LL cc=d^a[k].d^s[y]; if(mp[cc]==false) { p[++plen]=cc; mp[cc]=true; } } } } //---------------------------------------- LL lt[110]; bool cmp(LL p1,LL p2){return p1>p2;} void insert(LL k) { for(int i=62;i>=0;i--) if(k&(1LL<<i)) { if(lt[i]==0) {lt[i]=k;return ;} else k^=lt[i]; } } int main() { freopen("1.in","r",stdin); freopen("1.out","w",stdout); int x,y;LL d; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { scanf("%d%d%lld",&x,&y,&d); ins(x,y,d);ins(y,x,d); } ans=0;bk=false; memset(v,false,sizeof(v));v[1]=true; prdfs(1); plen=0; memset(s,-1,sizeof(s));s[1]=0; dfs(1,0); sort(p+1,p+plen+1,cmp); memset(lt,0,sizeof(lt)); for(int i=1;i<=plen;i++)insert(p[i]); for(int i=62;i>=0;i--)ans=max(ans,ans^lt[i]); printf("%lld ",ans); return 0; }