[bzoj4568] [loj#2013] [Scoi2016] 幸运数字

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 \leq20000,Q \leq 200000,Gi \leq 2^60\)

Output

输出需要包含 \(q\) 行，每行包含 \(1\) 个非负整数，表示这名旅行者可以保留的最大幸运值。

Sample Input

4 2

11 5 7 9

1 2

1 3

1 4

2 3

1 4

Sample Output

想法

要求一堆数中的最大异或和要用线性基。

那么这道题我们就要把一条路径上的所有店的值扔到线性基里去求最大。

怎么扔进去呢？倍增，维护每个点网上跳 \(2^i\) 个点这条链上的线性基

查询的时候 \(lca\) 的时候合并一下线性基就可以了。

没有卡常，极其感动。

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

using namespace std;

const int N = 20005;

typedef long long ll;

ll lread(){

	ll x=0;

	char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();

	return x;

}

int read(){

	int x=0;

	char ch=getchar();

	while(!isdigit(ch)) ch=getchar();

	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();

	return x;

}

int n;

ll G[N];

struct node{

	int v;

	node *nxt;

}pool[N*2],*h[N];

int cnt;

void addedge(int u,int v){

	node *p=&pool[++cnt],*q=&pool[++cnt];

	p->v=v;p->nxt=h[u];h[u]=p;

	q->v=u;q->nxt=h[v];h[v]=q;

}

int f[N][16],dep[N];

ll g[N][16][65];

void ins(ll *A,ll x) {

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

		if(x&(1ll<<i)){

			if(!A[i]) { A[i]=x; return; }

			x^=A[i];

		}

}

void merge(ll *A,ll *B) { for(int i=60;i>=0;i--) if(B[i]) ins(A,B[i]); }

ll MAX(ll *A) {

	ll ret=0;

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

	return ret;

}

void dfs(int u){

	int v;

	for(node *p=h[u];p;p=p->nxt)

		if(!dep[v=p->v]){

			dep[v]=dep[u]+1;

			f[v][0]=u; ins(g[v][0],G[u]);

			for(int j=1;j<16;j++){

				f[v][j]=f[f[v][j-1]][j-1];

				memcpy(g[v][j],g[v][j-1],sizeof(g[v][j]));

				merge(g[v][j],g[f[v][j-1]][j-1]);

			}

			dfs(v);

		}

}

ll lca(int x,int y){

	ll c[65]; memset(c,0,sizeof(c));

	ins(c,G[x]); ins(c,G[y]);

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

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

		if(dep[f[x][i]]>=dep[y]) merge(c,g[x][i]),x=f[x][i];

	if(x==y) return MAX(c);

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

		if(f[x][i]!=f[y][i]){

			merge(c,g[x][i]); x=f[x][i];

			merge(c,g[y][i]); y=f[y][i];

		}

	merge(c,g[x][0]);

	return MAX(c);

}

int main()

{

	int Q;

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

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

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

	dep[1]=1; dfs(1);

	while(Q--)

		printf("%lld\n",lca(read(),read()));

	return 0;

}

巴特西