题目链接

BZOJ4568

题解

选任意个数异或和最大，使用线性基

线性基插入\(O(logn)\)，合并\(O(log^2n)\)

我们要求树上两点间异或和最大值，由于合并是\(O(log^2n)\)的，我们尽量只合并一次

那就采用点分治

每次求出到分治重心的线性基，将过分治重心的询问的两个线性基合并即可

复杂度\(O(60^2q + 60nlogn)\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 20005,maxm = 200005,INF = 1000000000;

inline LL read(){

	LL out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

struct Bit{

	LL A[60];

	void init(){for (int i = 59; ~i; i--) A[i] = 0;}

	void copy(LL* B){for (int i = 59; ~i; i--) A[i] = B[i];}

	void ins(LL x){

		for (int i = 59; ~i; i--)

			if ((x >> i) & 1){

				if (A[i]) x ^= A[i];

				else {A[i] = x; break;}

			}

	}

	LL ask(){

		LL re = 0;

		for (int i = 59; ~i; i--) if ((re ^ A[i]) > re) re ^= A[i];

		return re;

	}

}B[maxn],T;

int h[maxn],ne = 1;

struct EDGE{int to,nxt;}ed[maxn << 1];

inline void build(int u,int v){

	ed[++ne] = (EDGE){v,h[u]}; h[u] = ne;

	ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;

}

int g[maxn],nxt[30 * maxm],tq[30 * maxn],cnt;

int n,q,x[maxm],y[maxm],vis[maxn],pos[maxn],Vis[maxn],now;

LL G[maxn],ans[maxm];

void Add(int u,int v){

	nxt[++cnt] = g[u]; tq[cnt] = v; g[u] = cnt;

}

int F[maxn],siz[maxn],fa[maxn],N,rt;

void getrt(int u){

	F[u] = 0; siz[u] = 1;

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		fa[to] = u; getrt(to);

		siz[u] += siz[to];

		F[u] = max(F[u],siz[to]);

	}

	F[u] = max(F[u],N - siz[u]);

	if (F[u] < F[rt]) rt = u;

}

void dfs(int u,int R){

	pos[u] = R; siz[u] = 1; Vis[u] = now;

	B[u].copy(B[fa[u]].A); B[u].ins(G[u]);

	Redge(u) if (!vis[to = ed[k].to] && to != fa[u]){

		fa[to] = u; dfs(to,R);

		siz[u] += siz[to];

	}

}

void solve(int u){

	F[rt = 0] = INF; N = siz[u]; getrt(u);

	//printf("u%d  rt%d\n",u,rt);

	pos[rt] = rt; vis[rt] = true; siz[u] = 1; Vis[rt] = ++now;

	B[rt].init(); B[rt].ins(G[rt]);

	Redge(rt) if (!vis[to = ed[k].to]){

		fa[to] = rt; dfs(to,to);

		siz[u] += siz[to];

	}

	for (int k = g[u],i,a,b; k; k = nxt[k]){

		i = tq[k]; a = x[i]; b = y[i];

		if (Vis[a] != now || Vis[b] != now) continue;

		if (pos[a] == pos[b]) Add(pos[a],i);

		else {

			T.copy(B[a].A);

			for (int j = 59; ~j; j--)

				if (B[b].A[j]) T.ins(B[b].A[j]);

			ans[i] = T.ask();

		}

	}

	Redge(rt) if (!vis[to = ed[k].to]){

		solve(to);

	}

}

int main(){

	n = read(); q = read();

	for (int i = 1; i <= n; i++) G[i] = read();

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

	for (int i = 1; i <= q; i++){

		x[i] = read(); y[i] = read();

		if (x[i] == y[i]) ans[i] = G[x[i]];

		else Add(1,i);

	}

	siz[1] = n; solve(1);

	for (int i = 1; i <= q; i++)

		printf("%lld\n",ans[i]);

	return 0;

}