给定一棵 $n$ 个点的树，点有点权 $\lt 2^{60}$，$q$ 次询问路径 $(u,v)$ 上任选点权，异或得到最大的权值。

看到选择元素，使得异或和最大自然想到线性基。
然后这是路径，考虑和主席树一样可持久化……可持久化线性基？开始玄幻了。
如果记录每个点到根的线性基呢？但线性基不能执行删除操作，也做不了。
……

既然不能删除那就直接合并。
暴力遍历路径上每个点然后扔进线性基。这显然不对。
能否通过记录一些额外的信息使得查询速度更快？例如多维护一些线性基。
那得先考虑如何合并两个线性基？显然直接暴力把一个线性基中的元素插入另一个线性基即可。

然后我们做一个类似于求 LCA 的事情：倍增。
对于每个点，我们存储它往上跳 $[0,2^k)$ 步到达点的集合的线性基，这样空间复杂度 $O(n \log n \log V)$。
查询就直接暴力跳倍增即可，这样总时间复杂度是 $O((n + q) \log n \log^2 V)$。

看上去有点悬。
复杂度瓶颈在哪里？在于询问的次数 $q$ 比较大。
但异或有一个很优美的性质：“对消”——$x \oplus x = 0$。
因此这类似于 RMQ 问题，对于 RMQ 的查询 $[l,r]$，只需要拿出 $[l,l+2^k)$ 和 $(r-2^k,r]$ 的倍增结果 $O(1)$ 合并即可。
那么对于 $(u,lca)$ 这条路径也一样，做一个类似于 ST 表的操作就可以 $O(\log^2 V)$ 合并出答案，另外一边 $(v,lca)$ 同理。
这样总复杂度就降到了 $O(n \log n \log^2 V + q \log^2 V)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5, M = N << 1;
int n, m, h[N], e[M], ne[M], idx = 0;
inline void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
long long a[N];

inline bool chk(long long x, int i) { return (x >> i) & 1; }
struct BIT {
    long long base[62];
    inline void insert(long long x) {
        if (!x) return;
        for (int i = 60; i >= 0; i--) {
            if (!chk(x, i)) continue;
            if (!base[i]) return base[i] = x, void();
            x ^= base[i];
        }
    }
    inline long long query() {
        long long res = 0;
        for (int i = 60; i >= 0; i--) res = max(res, res ^ base[i]);
        return res;
    }
};
inline BIT merge(BIT a, BIT b) {
    for (int i = 60; i >= 0; i--) a.insert(b.base[i]);
    return a;
}

int lg[N], fa[N][17], dep[N];
BIT bit[N][17];
void dfs(int u, int father) {
    fa[u][0] = father, dep[u] = dep[father] + 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i]; if (v == father) continue;
        dfs(v, u);
    }
}
void init() {
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= n; j++) fa[j][i] = fa[fa[j][i - 1]][i - 1];
    for (int i = 1; i <= n; i++) bit[i][0].insert(a[i]);
    for (int i = 1; i <= 15; i++)
        for (int j = 1; j <= n; j++) bit[j][i] = merge(bit[j][i - 1], bit[ fa[j][i - 1] ][i - 1]);
}

inline int lca(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (int i = 15; i >= 0; i--)
        if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    if (a == b) return a;
    for (int i = 15; i >= 0; i--)
        if (fa[a][i] ^ fa[b][i]) a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}

inline int getfa(int u, int k) {    // u 的 k 级祖先
    for (int i = 15; i >= 0; i--)
        if ((k >> i) & 1) u = fa[u][i];
    return u;
}

inline BIT get(int u, int v) { //v is u's parent
    if (u == v) return bit[u][0];
    int len = dep[u] - dep[v] + 1, k = lg[ len ];
    int l = getfa(u, len - (1 << k) );
    return merge(bit[u][k], bit[l][k]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), h[i] = -1;
    for (int i = 1, u, v; i < n; i++) scanf("%d%d", &u, &v), add(u, v), add(v, u);
    dfs(1, 1);
    init();
    while (m--) {
        int u, v, l; scanf("%d%d", &u, &v), l = lca(u, v);
        printf("%lld\n", merge(get(u, l), get(v, l)).query() );
    }
    return 0;
}