[SCOI2016] 幸運數字

利用線性基的合併，（直接暴力合併，複雜度62^2），當樹上路徑和來做。。。（然後跑的巨慢，但是可以優化哈哈）

#include <bits/stdc++.h>
using namespace std;

const int N=2e4+7;

struct XianXingJi {
    long long base[64];
    inline bool insert(long long vec) {
        for(int i=62; ~i; --i) {
            if(!(vec>>i)) continue;
            if(!base[i]) {base[i]=vec; return 1;}
            vec^=base[i];
        }
        return 0;
    }
    inline XianXingJi add(const XianXingJi& d) {
        XianXingJi res=*this;
        for(int i=62; ~i; --i) {
            if(d.base[i]) res.insert(d.base[i]);
        }
        return res;
    }
    inline long long max() {
        long long res=0;
        for(int i=62; ~i; --i) {
            if((res^base[i])>res) res^=base[i];
        }
        return res;
    }
} dis[N][20];

int n,m;
int fa[N][20],dep[N];
vector<int> e[N];

void pre(int x,int pa) {
    dep[x]=dep[fa[x][0]=pa]+1;
    for(int i=1; (1<<i)<=dep[x]; ++i) {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        dis[x][i]=dis[x][i-1].add(dis[fa[x][i-1]][i-1]);
    }
    for(int y:e[x]) if(y!=pa) {
        pre(y,x);
    }
}
long long query(int x,int y) {
    XianXingJi res;
    memset(&res,0,sizeof res);
    if(dep[x]<dep[y]) swap(x,y);
    int dif=dep[x]-dep[y];
    for(int i=19; ~i; --i) {
        if(dif&(1<<i)) {
            res=res.add(dis[x][i]), x=fa[x][i];
        }
    }
    if(x==y) return res.add(dis[x][0]).max();
    for(int i=19; ~i; --i) {
        if(fa[x][i]!=fa[y][i]) {
            res=res.add(dis[x][i]), x=fa[x][i];
            res=res.add(dis[y][i]), y=fa[y][i];
        }
    }
    res=res.add(dis[x][0]).add(dis[y][1]);
    return res.max();
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        long long x;
        scanf("%lld",&x);
        dis[i][0].insert(x);
    }
    for(int i=n,x,y; --i; ) {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    pre(1,0);
    for(int i=m,x,y; i--; ) {
        scanf("%d%d",&x,&y);
        printf("%lld\n",query(x,y));
    }
    return 0;
}