写了一天啊，调了好久，对拍了无数次都拍不出错来(数据生成器太弱了没办法啊)。
错误1：把线性基存成结构体，并作为函数计算，最后赋值给调用函数的变量时无疑加大了计算量导致TLE
错误2：像这种函数(A,B,C)功能是实现C=A+B，而要计算A=A+B时千万不能(A,B,A)这么用QAQ，它不会存储A之前的值用来计算新的A的值啊，因为这个出现了许多奇奇怪怪的错误ovo
错误3：错误答案，调起来非常令人崩溃，从Tyrant那里要了SCOI的数据后查错，面对一大堆数字怎么可能查出错来。只好静态查错，呆看程序2h+，最后看了网上的一篇题解，发现别人合并线性基时开的数组非常大，而我是卡着60开的。如果两个长为60的线性基合并前存储到长为60的线性基里不错才怪呢QuQ，开成了120才卡过QAQ。
犯逗了一天，其实这道题也不是很难，只是我手残打出的各种错误使Debug浪费了太多时间。
这道题重点在于合并线性基，会合并线性基的话倍增的方法应该不难想。预处理出倍增数组，每次倍增找LCA，然后用4个存倍增长度的链上的线性基合并，最后贪心算出答案，总时间复杂度为$O(N\log N×P^2+Q(\log N+3×P^2))$，其中因为数据是long long范围内的，所以$P=60$。这么小的P可以视为常数而我却把它算在时间复杂度里，我果然还想继续犯逗TwT
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 20003;
LL getLL() {
LL k = 0; int fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 1) + (k << 3) + c - '0';
return k * fh;
}
int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = (k << 1) + (k << 3) + c - '0';
return k * fh;
} int point[N], n, cnt = 0, fa[N][16], deep[N];
struct node {int nxt, to;} E[N << 1];
struct LineB {int n; LL A[61];};
LL S[121];
void Merge(LineB x, LineB y, LineB &c) {
int i, tmp = 0, num;
num= x.n + y.n;
for(i = 1; i <= x.n; ++i)
S[i] = x.A[i];
for(i = x.n + 1; i <= num; ++i)
S[i] = y.A[i - x.n];
for(LL j = (1LL << 60); j; j >>= 1) {
for(i = tmp + 1; i <= num; ++i)
if (S[i] & j)
break;
if (i > num) continue;
swap(S[++tmp], S[i]);
for(i = 1; i <= num; ++i)
if (i != tmp && S[i] & j)
S[i] ^= S[tmp];
}
c.n = tmp;
for(i = 1; i <= tmp; ++i)
c.A[i] = S[i];
} LineB J[N][16];
void ins(int x, int y) {E[++cnt].nxt = point[x]; E[cnt].to = y; point[x] = cnt;}
void _(int x, int f) {
fa[x][0] = f; deep[x] = deep[f] + 1;
for(int i = 1; i <= 15; ++i) {
fa[x][i] = fa[fa[x][i - 1]][i - 1];
Merge(J[x][i - 1], J[fa[x][i - 1]][i - 1], J[x][i]);
}
for(int tmp = point[x]; tmp; tmp = E[tmp].nxt)
if (E[tmp].to != f)
_(E[tmp].to, x);
} int Log2[N];
int __(int x, int y) {
for(int i = 15; i >= 0; --i)
if ((1 << i) & y) x = fa[x][i];
return x;
}
int LCA(int x, int y) {
if (deep[x] < deep[y]) swap(x, y);
int k = deep[x] - deep[y];
for(int i = 0; i <= 15; ++i)
if (k & (1 << i)) x = fa[x][i];
if (x == y) return x;
for(int i = 15; i >= 0; --i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}
LL ___(LineB x) {
LL ret = 0;
for(int i = 1; i <= x.n; ++i)
ret ^= x.A[i];
return ret;
}
int main() {
n = getint(); int Q = getint();
for(int i = 1; i <= n; ++i) {
J[i][0].n = 1;
J[i][0].A[1] = getLL();
} int x, y;
for(int i = 1; i < n; ++i) {
x = getint(); y = getint();
ins(x, y); ins(y, x);
} _(1, 0);
x = 0;
for(int i = 1; i <= n; ++i) {
if (1 << x == i)
++x;
Log2[i] = x - 1;
} for(int i = 1; i <= Q; ++i) {
x = getint(); y = getint();
int lca = LCA(x, y), lx = deep[x] - deep[lca] + 1, ly = deep[y] - deep[lca] + 1;
int logx = Log2[lx], logy = Log2[ly];
LineB X; Merge(J[x][logx], J[__(x, lx - (1 << logx))][logx], X);
LineB Y; Merge(J[y][logy], J[__(y, ly - (1 << logy))][logy], Y);
LineB Z; Merge(X, Y, Z);
printf("%lld\n", ___(Z));
} return 0;
}
CTSC 2016 Day-2 Bless All