bzoj4568:[Scoi2016]幸运数字(倍增+线性基)

Author Avatar
Sakits 4月 19, 2018

题解

  用倍增维护一下自己到2i2^i倍祖先路径上的数的线性基,合并的时候暴力就行了,复杂度O(602nlogn)O(60^2nlogn)
  不知道怎么搞可以变成一个6060,反正我写的两个6060
  把倍增那维放前面之后反而不能用一个子程序来搞所有合并操作了,只好写了两段几乎相同的代码,结果跑的好像还比倍增那维放后面慢,最后代码又长又慢= =…唉,人老了佛系了,没被卡常就对常数没追求了,会写就行了就这样吧…

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
#define ll long long
using namespace std;
const int maxn=20010, inf=1e9;
struct edge{int too, pre;}e[maxn<<1];
int tot;
ll n, Q, x, y;
int last[maxn], f[20][maxn], d[maxn];
ll a[maxn], b[20][63][maxn], ans[63];

inline void read(ll &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}

void dfs(int x)
{
	if(a[x]) b[0][(int)log2(a[x])][x]=a[x]; d[x]=d[f[0][x]]+1;
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=f[0][x]) f[0][too]=x, dfs(too);
}

inline void init()
{
	for(int j=1;j<=15;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[j][i]=f[j-1][f[j-1][i]];
			int fa=f[j-1][i];
			for(int k=60;~k;k--) b[j][k][i]=b[j-1][k][i];
			for(int k=60;~k;k--)
			{
				ll p=b[j-1][k][fa];
				if(!p) continue;
				for(int l=60;~l;l--)
				if((p>>l)&1)
				{
					if(b[j][l][i]) p^=b[j][l][i];
					else {b[j][l][i]=p; break;}
				}
			}
		}
	}
}

inline void merge(int i, int x)
{
	for(int j=60;~j;j--)
	{
		ll p=b[i][j][x]; 
		if(!p) continue;
		for(int k=60;~k;k--)
		if((p>>k)&1)
		{
			if(ans[k]) p^=ans[k];
			else {ans[k]=p; break;}
		}
	}
}

inline ll queryans()
{
	ll ANS=0;
	for(int i=60;~i;i--) 
	if(!((ANS>>i)&1)) ANS^=ans[i];
	return ANS;
}

inline ll query(int x, int y)
{
	for(int i=0;i<=60;i++) ans[i]=0;
	if(d[x]<d[y]) swap(x, y);
	for(int i=15;~i;i--) 
	if(d[f[i][x]]>=d[y]) merge(i, x), x=f[i][x];
	if(x==y) return merge(0, x), queryans();
	for(int i=15;~i;i--)
	if(f[i][x]!=f[i][y]) merge(i, x), merge(i, y), x=f[i][x], y=f[i][y];
	merge(1, x); merge(0, y);
	return queryans();
}

int main()
{
	read(n); read(Q);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);
	dfs(1); init();
	while(Q--) read(x), read(y), printf("%lld\n", query(x, y));
}