Description
A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个
幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 A 国。旅行者计划
乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。
在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸
运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，
游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。
有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5
和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中
可以保留的最大幸运值是多少。
Input
第一行包含 2 个正整数 n ，q，分别表示城市的数量和旅行者数量。第二行包含 n 个非负整数，其中第 i 个整
数 Gi 表示 i 号城市的幸运值。随后 n-1 行，每行包含两个正整数 x ，y，表示 x 号城市和 y 号城市之间有一
条道路相连。随后 q 行，每行包含两个正整数 x ，y，表示这名旅行者的旅行计划是从 x 号城市到 y 号城市。N
<=20000,Q<=200000,Gi<=2^60
Output
输出需要包含 q 行，每行包含 1 个非负整数，表示这名旅行者可以保留的最大幸运值。
题目分析
树剖/倍增的板子题
想用树剖来做一做，然而TLE了好几发。
发现自己常数意识太差，每次query时候都开一个线性基，活生生浪费10s+
#include<bits/stdc++.h>
#define ENS //__attribute__((optimize("-O2")))
#define NES //__attribute__((optimize("-O2"))) //__inline__ __attribute__((always_inline))
typedef long long ll;
const int maxn = ;
const int maxm = ;
const int maxq = ; struct Linear
{
ll p[];
Linear(){memset(p, , sizeof p);}
NES void insert(ll c)
{
for (int i=, chk=; i>=&&!chk; i--)
if (c>>i){
if (p[i]) c ^= p[i];
else p[i] = c, chk = ;
}
}
NES void merge(Linear b)
{
for (int i=; i>=; i--)
if (b.p[i]) insert(b.p[i]);
}
NES ll max()
{
ll ret = ;
for (int i=; i>=; i--)
if ((ret^p[i]) > ret) ret ^= p[i];
return ret;
}
}f[maxn<<];
struct node
{
int fa,son,top,tot;
}a[maxn];
int n,q,chain[maxn],chTot,dep[maxn];
int edgeTot,head[maxn],nxt[maxm],edges[maxm];
ll g[maxn],cnVal[maxn]; template <typename T> NES void read(T&x)
{
char cu=getchar();x=;bool fla=;
while(!isdigit(cu)){if(cu=='-')fla=;cu=getchar();}
while(isdigit(cu))x=x*+cu-'',cu=getchar();
if(fla)x=-x;
}
void write(ll x){if (x/) write(x/);putchar(''+x%);}
void writeln(ll x){write(x), putchar('\n');}
NES void addedge()
{
int u,v;
read(u), read(v);
edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
edges[++edgeTot] = u, nxt[edgeTot] = head[v], head[v] = edgeTot;
}
void dfs1(int x, int fa)
{
a[x].son = a[x].top = -, a[x].fa = fa;
a[x].tot = , dep[x] = dep[fa]+;
for (int i=head[x]; i!=-; i=nxt[i])
{
int v = edges[i];
if (v!=fa){
dfs1(v, x), a[x].tot += a[v].tot;
if (a[x].son==-||a[a[x].son].tot < a[v].tot) a[x].son = v;
}
}
}
void dfs2(int x, int top)
{
a[x].top = top, chain[x] = ++chTot, cnVal[chTot] = g[x];
if (a[x].son==-) return;
dfs2(a[x].son, top);
for (int i=head[x]; i!=-; i=nxt[i])
{
int v = edges[i];
if (v!=a[x].son&&v!=a[x].fa) dfs2(v, v);
}
}
void build(int rt, int l, int r)
{
if (l==r){
f[rt].insert(cnVal[l]);
return;
}
int mid = (l+r)>>;
build(rt<<, l, mid);
build(rt<<|, mid+, r);
f[rt] = f[rt<<], f[rt].merge(f[rt<<|]);
}
Linear query(int rt, int l, int r, int L, int R)
{
if (L <= l&&r <= R) return f[rt];
int mid = (l+r)>>;
if (L <= mid&&R > mid){ Linear tmp = query(rt<<, l, mid, L, R);
tmp.merge(query(rt<<|, mid+, r, L, R));
return tmp;
}else if (L <= mid) return query(rt<<, l, mid, L, R);
else if (R > mid) return query(rt<<|, mid+, r, L, R);
}
NES void queryChain()
{
Linear ret;
int x,y;
read(x), read(y);
while (a[x].top!=a[y].top)
{
if (dep[a[x].top] > dep[a[y].top]) std::swap(x, y);
ret.merge(query(, , n, chain[a[y].top], chain[y]));
y = a[a[y].top].fa;
}
if (dep[x] > dep[y]) std::swap(x, y);
ret.merge(query(, , n, chain[x], chain[y]));
writeln(ret.max());
}
ENS int main()
{
memset(head, -, sizeof head);
read(n), read(q);
for (int i=; i<=n; i++) read(g[i]);
for (int i=; i<n; i++) addedge();
dfs1(, ), dfs2(, );
build(, , n);
while (q--) queryChain();
return ;
}
END