题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器：http://paste.ubuntu.com/23202923/
《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看，结果最开始写的是链剖，T到死 ←是男人就去ZGS的OJ上测，单点时限
后来重新写了LCA的版本，又T到死
于是暴力优化常数，最终5.9s勉强卡过
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 20000+9;
int n,q,head[N],nxt[N*2],to[N*2];
LL arr[N];
inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;}
inline void Add_Edge(int u, int v) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T;
to[++T] = u; nxt[T] = head[v]; head[v] = T;
}
namespace LCA{
int fa[N][16],dep[N];
LL f[N][16][61],POW[61];
void DFS(int w, int f) {
fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w);
} inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;}
inline void merge(LL *a, LL *b) {
for (int i=60;~i;i--) if (b[i]) {
LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) {
if (!a[j]) {a[j] = w; break;}
else w ^= a[j];
}
}
}
inline void init() {
for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;}
for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]);
for (int i=1;i<=n;i++) for (int j=2;j<=15;j++)
fa[i][j] = fa[fa[i][j-1]][j-1],
memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])),
merge(f[i][j],f[fa[i][j-1]][j-1]);
}
inline LL query(int x, int y) {
static LL bas[61]; memset(bas,0,sizeof(bas));
if (dep[x] < dep[y]) swap(x,y);
for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y])
merge(bas,f[x][i]), x = fa[fa[x][i]][1];
if (x == y) merge(bas,f[x][0]);
else {
for (int i=15;~i;i--) if (fa[x][i] != fa[y][i])
merge(bas,f[x][i]), merge(bas,f[y][i]),
x = fa[fa[x][i]][1], y = fa[fa[y][i]][1];
merge(bas,f[x][0]);
} LL ret = 0;
for (int i=0;i<=60;i++) if (bas[i])
for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i];
for (int i=0;i<=60;i++) ret ^= bas[i];
return ret;
}
};
int main(){
n = read(); q = read();
for (int i=1;i<=n;i++) arr[i] = readL();
for (int i=1;i<n;i++) Add_Edge(read(),read());
LCA::DFS(); LCA::init();
for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read()));
return 0;
}
另外，%Claris，直接上点分治：http://www.cnblogs.com/clrs97/p/5451814.html
