大意

找1到n的路径中异或和最大的路径。

分析

首先，我们考虑这样一个问题：

先看另一道题

N个点M条边的边带权的无向图，求一个回路使XOR和最大(回路中的路径可以走多次)。

另一道题的分析

有这样一个结论（从这里到证明结束的所说回路只能走一次）

两个回路的和仍是回路(‘和’ 指 ‘异或和’/‘对称差’)

一个无向连通图G中有且仅有M-N+1个独立回路。

那什么是独立的回路呢，就是一个不能由其他的回路通过异或得到的回路。

对结论的证明：

M=N-1时，就是树，有0个回路，结论成立。

用数学归纳法进行证明

设M=K时结论成立，即有K-N+1个独立回路，当M=K+1时，设M=K时图为G，新加了一条边e，任取一个包含e的回路C，显然是一个独立的回路。

任意两个包含e的回路C1与C2，C1,2=C1^C2是G中的回路，C2=C1,2^C1，所以C2不是独立的回路，由此先可以证得其他包含e的回路也不是独立的回路，故能且仅能增加一个包含e的独立回路。

所以，每增加一条边，只增加一个回路。

从而G中恰有(K+1)-N+1个独立回路，证毕。

这些独立的回路互相异或，我们就可以得到任何一个回路的值(因为其他回路都可以由这些回路异或得到)。

所以，我们只需要找到所有的独立回路即可。

找的方法：

即随便生成一棵生成树，任选根，处理出每个节点到根的路径的异或和sumi。然后对于每一条非树边(u,v,wt)，我们可以通过sumu^sumv^wt来求出包含当前边的一个回路的异或和。

然后，我们就可以用那道题的做法来解决了。

如果两个回路不相交怎么办？没关系，我们将两个回路直接连接一条路径，也会得到一个回路，显然连接的这条路径会经过两次，对答案没有贡献

回到这道题

那和这道题有什么关系呢，我们在S和T直接连一条权值为0的边，显然我们就可以求经过这条边的回路的异或和(设为s0)的最大值即可。

所以，我们只需要保证包含这条边的独立回路一定被选择即可。

因为要所以，保证包含这条边的独立回路一定被选择，我们每次尝试使i方程的右边等于1^(S0的第i位即可)，

也只能用的第二种解法。

代码

#include
     
      #include
      
       #include
       
        using namespace std;#define MAXN 50000#define MAXM 100000#define D 32typedef long long LL;typedef unsigned int uint;int n,m,fa[MAXN+10],var,equ=60,c[MAXM+10];uint a[60][MAXM/D+10];LL sum[MAXN+10],b[MAXM+10],ans,cl;struct node{    int v;    LL wt;    bool f;    node *next;}*adj[MAXN+10],edge[MAXM*2+10],*ecnt=edge;struct node2{    int u,v;    LL wt;    bool f;    node2(){    }    node2(int uu,int vv,LL wwt,bool ff){        u=uu,v=vv,wt=wwt,f=ff;    }}ednm[MAXM+10];template
        
         void Read(T &x){    char c;    while(c=getchar(),c!=EOF)        if(c>='0'&&c<='9'){            x=c-'0';            while(c=getchar(),c>='0'&&c<='9')                x=x*10+c-'0';            ungetc(c,stdin);            return;        }}void addedge(int u,int v,LL wt,bool f){    node *p=++ecnt;    p->wt=wt;    p->v=v;    p->f=f;    p->next=adj[u];    adj[u]=p;}int find(int x){    return fa[x]==x?x:fa[x]=find(fa[x]);}void read(){    Read(n),Read(m);    int i,u,v;    LL wt;    for(i=1;i<=n;i++)        fa[i]=i;    for(i=1;i<=m;i++){        Read(u),Read(v),Read(wt);        if(find(u)!=find(v)){            fa[fa[u]]=fa[v];            addedge(u,v,wt,1);            addedge(v,u,wt,1);            ednm[i]=node2(u,v,wt,1);        }        else{            addedge(u,v,wt,0);            addedge(v,u,wt,0);            ednm[i]=node2(u,v,wt,0);        }    }}void dfs(int u,int fa){    for(node *p=adj[u];p;p=p->next)        if(p->f&&p->v!=fa){            sum[p->v]=sum[u]^p->wt;            dfs(p->v,u);        }}void prepare(){    int i,j;    for(i=1;i<=m;i++)        if(!ednm[i].f)            b[var++]=ednm[i].wt^sum[ednm[i].u]^sum[ednm[i].v];    for(i=1;i<=equ;i++)        for(j=0;j
         
          >(equ-i)&1)<<(j%D);    cl=sum[n];}void gaussian_elimination(){    int row,i,j,qv1=var/D,qv2=var%D;    for(row=1;row<=equ;row++){        a[row][qv1]|=(((cl>>(equ-row))&1)^1)<