题解

最大异或和，明显是个线性基

然而还有那么多路径……那就树分治，反正点数看起来很少，就是为了让人乘上一个60的常数嘛

把一个树的点分树记录下来，然后看看询问的两个点彼此相同的最后一个父亲是谁，把这个询问挂在这个点上，计算就暴力搜索这棵树里每一个节点到重心的线性基就行了，最后再用60的常数把两个线性基合起来

代码

#include 
    
     //#define ivorysi#define MAXN 20005#define MAXQ 200005typedef long long int64;typedef unsigned int u32;using namespace std;struct node {    int to,next;}edge[MAXN * 2];int head[MAXN],sumE,n,m;int64 val[MAXN];vector
     
       aux[MAXN],qry[MAXN];bool vis[MAXN];int que[MAXN],qr,ql;int siz[MAXN],son[MAXN],fa[MAXN];int st[MAXQ],ed[MAXQ];int64 dp[MAXN][65],ans[MAXQ];void add(int u,int v) {    edge[++sumE].to = v;    edge[sumE].next = head[u];    head[u] = sumE;}void addtwo(int u,int v) {    add(u,v);add(v,u);}int calc_G(int u) {    que[ql = qr = 1] = u;    fa[u] = 0;    while(ql <= qr) {    int now = que[ql++];    siz[now] = 1;son[now] = 0;    for(int i = head[now] ; i ; i = edge[i].next) {        int v = edge[i].to;        if(!vis[v] && fa[now] != v) {        que[++qr] = v;        fa[v] = now;        }    }    }    int res = que[qr];    for(int i = qr ; i >= 1 ; --i) {    int now = que[i];    siz[fa[now]] += siz[now];    if(siz[now] > son[fa[now]]) son[fa[now]] = siz[now];    if(qr - siz[now] > son[now]) son[now] = qr - siz[now];    if(son[now] < son[res]) res = now;    }    return res;}void dfs(int u) {    int G = calc_G(u);    vis[G] = 1;    for(int i = 1 ; i <= qr ; ++i) aux[que[i]].push_back(G);    for(int i = head[G] ; i ; i = edge[i].next) {    int v = edge[i].to;    if(!vis[v]) dfs(v);    }}void Init() {    scanf("%d%d",&n,&m);    for(int i = 1 ; i <= n ; ++i) scanf("%lld",&val[i]);    int u,v;    for(int i = 1 ; i < n ; ++i) {    scanf("%d%d",&u,&v);    addtwo(u,v);    }    dfs(1);    for(int i = 1 ; i <= m ; ++i) {    scanf("%d%d",&st[i],&ed[i]);    if(st[i] == ed[i]) ans[i] = val[st[i]];    }    for(int i = 1 ; i <= m ; ++i) {    if(st[i] == ed[i]) continue;    int s = min(aux[st[i]].size(),aux[ed[i]].size());    bool flag = false;    for(int j = 0 ; j < s ; ++j) {        if(aux[st[i]][j] != aux[ed[i]][j]) {        qry[aux[st[i]][j - 1]].push_back(i);        flag = 1;        break;        }    }    if(!flag) qry[aux[st[i]][s - 1]].push_back(i);    }}void insert(int id,int64 v) {    for(int j = 60 ; j >= 0 ; --j) {    if(v >> j & 1) {        if(dp[id][j]) v ^= dp[id][j];        else {        dp[id][j] = v;        for(int k = 60 ; k > j ; --k) {            if(dp[id][k] >> j & 1) dp[id][k] ^= dp[id][j];        }        break;        }    }    }}void calc(int u) {    que[ql = qr = 1] = u;    fa[u] = 0;    memset(dp[u],0,sizeof(dp[u]));    while(ql <= qr) {    int now = que[ql++];    for(int i = head[now] ; i ; i = edge[i].next) {        int v = edge[i].to;        if(!vis[v] && fa[now] != v) {        fa[v] = now;        memcpy(dp[v],dp[now],sizeof(dp[now]));        insert(v,val[v]);        que[++qr] = v;        }    }    }}void Process(int u) {    for(auto k : aux[u]) vis[u] = 1;    calc(u);        for(auto k : qry[u]) {    memset(dp[n + 1],0,sizeof(dp[n + 1]));    insert(n + 1,val[u]);    for(int i = 0 ; i <= 60 ; ++i) {        if(dp[st[k]][i]) insert(n + 1,dp[st[k]][i]);        if(dp[ed[k]][i]) insert(n + 1,dp[ed[k]][i]);    }    for(int i = 60 ; i >= 0 ; --i) {        if(!dp[n + 1][i]) continue;        if(!(ans[k] >> i & 1)) ans[k] ^= dp[n + 1][i];    }    }    for(auto k : aux[u]) vis[u] = 0;}void Solve() {    memset(vis,0,sizeof(vis));    for(int i = 1 ; i <= n ; ++i) {    if(qry[i].size() != 0) {        Process(i);    }    }    for(int i = 1 ; i <= m ; ++i) {    printf("%lld\n",ans[i]);    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Init();    Solve();}