Xortest Path

题意：求任意两点的异或最短路

思路：
假设点x到点y必须经过一条边，那么它可以通过走环来减少路径的异或和(如果和环的异或值 异或后更小)
如图，
特别的
即

我们可以先以1为根，建一颗树，跑出1到所有点的异或值，此时往树中加边一定会形成一个环，所以在建树时没有跑过的边对应一个环，这个环的异或值为。
按二进制存环的异或值，一般情况，环的异或值二进制最高位为第位则存在中；特别的，当存了一个或多个环时，，如果下一位为空则存入反之继续。假如两个环的异或值最高为都是第位，分别为，假设处理后，那么表示的是这两个环都走一遍，而可以通过得到。

接下来计算任意两个点的异或最短路,假设，我们要求的就是走那些环可以减少dis的值，从而得到异或最短路。前面已经按二进制位预处理了所有环的异或值，只要按二进制位最高位从高到低考虑，不断取最小值，考虑到的是先消去dis的高位一定是最优的，所以不能从低到高来。

MyCode:

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+7,maxm=2e5+7,N=1e5+7;
typedef long long int ll;
typedef unsigned long long ull;
int head[maxn],x[N],y[N],to[maxm],id[maxm],Next[maxm],tot;
ll val[maxm],edg[N];
inline void add(int a,int b,ll v) {
    to[++tot]=b;
    Next[tot]=head[a];
    val[tot]=v;
    head[a]=tot;
}
ll d[maxn],a[60],pw[60];
bool vis[maxn],f[N];
void dfs(int x) {
    vis[x]=true;
    for(int i=head[x],k=to[i];i;i=Next[i],k=to[i]) {
        if(!vis[k]) {
            d[k]=d[x]^val[i];
            f[id[i]]=1;
            dfs(k);
        }
    }
}
void ins(ll x) {
    for(int i=59;~i;--i) {
        if(pw[i]&x)  {
            if(a[i]) x^=a[i];
            else {
                a[i]=x;
                break;
            }
        }
    }
}
ll solve(ll x) {
    for(int i=59;~i;--i) if(a[i])
        x=min(x,x^a[i]);
    return x;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    pw[0]=1;
    for(int i=1;i<=59;++i) pw[i]=pw[i-1]<<1;
    int n,m,Q;
    cin>>n>>m>>Q;
    for(int i=1;i<=m;++i) {
        cin>>x[i]>>y[i]>>edg[i];
        add(x[i],y[i],edg[i]);id[tot]=i;
        add(y[i],x[i],edg[i]);id[tot]=i;
    }
    dfs(1);
    for(int i=1;i<=m;++i) if(!f[i]) ins(d[x[i]]^d[y[i]]^edg[i]);
    int xx,yy;
    while(Q--) {
        cin>>xx>>yy;
        cout<<solve(d[xx]^d[yy])<<'\n';
    }
    return 0;;
}