luoguP3292 [SCOI2016]幸运数字(倍增做法)

题意

线性基套上树上倍增即可，注意边界。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=20010;
int n,m,cnt,t;
int head[maxn],dep[maxn];
int f[maxn][20];
ll a[maxn];
struct edge{int to,nxt;}e[maxn<<1];
struct Xord
{
	ll d[65];
	Xord(){memset(d,0,sizeof(d));}
	inline void insert(ll x)
	{
		for(int i=60;~i;i--)
		{
			if(!(x&(1ll<<i)))continue;
			if(!d[i]){d[i]=x;return;}
			else x^=d[i];
		}
	}
	inline ll query()
	{
		ll res=0;
		for(int i=60;~i;i--)res=max(res,res^d[i]);
		return res;
	}
}xord[maxn][20];
inline void add(int u,int v)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	for(int i=1;i<=t;i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		for(int j=0;j<=60;j++)xord[x][i].d[j]=xord[x][i-1].d[j];
		for(int j=0;j<=60;j++)if(xord[f[x][i-1]][i-1].d[j])xord[x][i].insert(xord[f[x][i-1]][i-1].d[j]);
	}
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==fa)continue;
		f[y][0]=x;dfs(y,x);
	}
}
inline ll query(int x,int y)
{
	Xord res;
	if(dep[x]>dep[y])swap(x,y);
	for(int i=t;~i;i--)
		if(dep[f[y][i]]>=dep[x])
		{
			for(int j=0;j<=60;j++)if(xord[y][i].d[j])res.insert(xord[y][i].d[j]);
			y=f[y][i];
		}
	if(x==y)
	{
		res.insert(a[x]);
		return res.query();
	}
	for(int i=t;~i;i--)
		if(f[x][i]!=f[y][i])
		{
			for(int j=0;j<=60;j++)if(xord[x][i].d[j])res.insert(xord[x][i].d[j]);
			for(int j=0;j<=60;j++)if(xord[y][i].d[j])res.insert(xord[y][i].d[j]);
			x=f[x][i],y=f[y][i];
		}
	res.insert(a[x]),res.insert(a[y]),res.insert(a[f[x][0]]);
	return res.query();
}
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);t=(int)log2(n)+1;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),xord[i][0].insert(a[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		printf("%lld
",query(x,y));
	}
	return 0;
}