4568: [Scoi2016]幸运数字

题意：一颗带点权的树，求树上两点间异或值最大子集的异或值

---

显然要用线性基

可以用倍增的思想，维护每个点向上\(2^j\)个祖先这些点的线性基，求lca的时候合并起来就行了

复杂度\(O(nlogn60*60)\)

注意这是点权，特判x==y的情况，需要插入a[x]

还可以用点分治和树链剖分

我的代码好慢啊...但是很好写啊

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define fir first

#define sec second

const int N=2e4+5;

inline ll read() {

    char c=getchar(); ll x=0, f=1;

    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, Q, u, v; ll a[N];

struct edge{int v, ne;}e[N<<1];

int cnt=1, h[N];

inline void ins(int u, int v) {

	e[++cnt]=(edge){v, h[u]}; h[u]=cnt;

	e[++cnt]=(edge){u, h[v]}; h[v]=cnt;

}

namespace lb{

	struct meow {

		ll p[62];

		meow(){memset(p, 0, sizeof(p));}

		ll operator [](int x) {return p[x];}

		bool insert(ll val) {

			for(int i=60; i>=0; i--)

				if(val & (1LL<<i)) {

					if(p[i]) val ^= p[i];

					else {p[i]=val; break;}

				}

			return val>0;

		}

		void merge(meow &a) {

			for(int i=60; i>=0; i--) if(a[i]) insert(a[i]);

		}

		ll getmax() {

			ll ans=0;

			for(int i=60; i>=0; i--) ans = max(ans, ans^p[i]);

			return ans;

		}

		void print() {

			for(int i=60; i>=0; i--) if(p[i]) printf("p %d %lld\n",i,p[i]);

			puts("");

		}

	}b[N][17];

}using lb::b; using lb::meow;

int fa[N][17], deep[N];

void dfs(int u) {

	for(int i=1; (1<<i)<=deep[u]; i++) {

		fa[u][i] = fa[ fa[u][i-1] ][i-1];

		b[u][i].merge(b[u][i-1]); b[u][i].merge(b[ fa[u][i-1] ][i-1]);

	}

	for(int i=h[u];i;i=e[i].ne)

		if(e[i].v != fa[u][0]) {

			fa[e[i].v][0]=u;

			deep[e[i].v]=deep[u]+1;

			b[e[i].v][0].insert(a[u]);

			dfs(e[i].v);

		}

}

meow lca(int x, int y) { //printf("lca %d %d\n",x,y);

	meow now;

	if(x==y) {now.insert(a[x]); return now;}

	if(deep[x]<deep[y]) swap(x, y);

	int bin=deep[x]-deep[y];

	for(int i=0; i<15; i++)

		if((1<<i)&bin) now.merge(b[x][i]), x=fa[x][i];

	if(x==y) return now;

	for(int i=14; i>=0; i--)

		if(fa[x][i] != fa[y][i]) now.merge(b[x][i]), now.merge(b[y][i]), x=fa[x][i], y=fa[y][i];

	now.merge(b[x][0]); now.insert(a[y]);

	//puts("now");now.print();

	return now;

}

ll Que(int x, int y) {

	return lca(x, y).getmax();

}

int main() {

	freopen("in","r",stdin);

	n=read(); Q=read();

	for(int i=1; i<=n; i++) a[i]=read(), b[i][0].insert(a[i]);

	for(int i=1; i<n; i++) ins(read(), read());

	dfs(1);

	//for(int i=1; i<=n; i++)

	//	for(int j=0; (1<<j)<=deep[i]; j++) printf("hi %d  %d %d\n",i,j,fa[i][j]), b[i][j].print();

	for(int i=1; i<=Q; i++) printf("%lld\n", Que(read(), read()));

}