luoguP3292 [SCOI2016]幸运数字(点分治做法)

题意

考虑点分治，每次处理过重心的询问（即两点在重心的不同子树中）。

求出每个点到重心的线性基，之后对过重心的询问合并两点线性基求解。

code:

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mkp make_pair
#define fir first
#define sec second
typedef long long ll;
const int maxn=20010;
const int maxm=200010;
const int inf=1e9;
int n,m,cnt,root,maxsize=inf,trsize;
int head[maxn],size[maxn],check[maxn];
ll a[maxn],ans[maxm];
bool vis[maxn];
vector<pii>ve[maxn];
struct edge{int to,nxt;}e[maxn<<1];
struct Xord
{
	ll d[65];
	Xord(){memset(d,0,sizeof(d));}
	inline void clear(){memset(d,0,sizeof(d));}
	inline void insert(ll x)
	{
		for(int i=61;~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=61;~i;i--)res=max(res,res^d[i]);
		return res;
	}
}xord[maxn];
inline void add(int u,int v)
{
	e[++cnt].nxt=head[u];
	head[u]=cnt;
	e[cnt].to=v;
}
void getroot(int x,int fa)
{
	size[x]=1;
	int maxx=0;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==fa||vis[y])continue;
		getroot(y,x);size[x]+=size[y];
		maxx=max(maxx,size[y]);
	}
	maxx=max(maxx,trsize-size[x]);
	if(maxx<maxsize)maxsize=maxx,root=x;
}
void getxor(int x,int fa)
{
	xord[x]=xord[fa];xord[x].insert(a[x]);
	for(unsigned int i=0;i<ve[x].size();i++)
	{
		int y=ve[x][i].fir;
		if(check[y]!=root)continue;
		Xord tmp=xord[x];
		for(int j=0;j<=60;j++)if(xord[y].d[j])tmp.insert(xord[y].d[j]);
		ans[ve[x][i].sec]=max(ans[ve[x][i].sec],tmp.query());
	}
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==fa||vis[y])continue;
		getxor(y,x);
	}
}
void mark(int x,int fa,int k)
{
	check[x]=k;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(y==fa||vis[y])continue;
		mark(y,x,k);
	}
}
void solve(int x)
{
	//cerr<<x<<endl;
	vis[x]=1;check[x]=x;
	xord[x].clear();xord[x].insert(a[x]);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(vis[y])continue;
		getxor(y,x);mark(y,x,x);
	}
	for(int i=head[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		if(vis[y])continue;
		maxsize=inf;trsize=size[y];getroot(y,0);
		solve(root);
	}
}
int main()
{
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}	
	for(int i=1;i<=m;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		if(x==y)ans[i]=a[x];
		else ve[x].push_back(mkp(y,i)),ve[y].push_back(mkp(x,i));
	}
	trsize=n;maxsize=inf;getroot(1,0);
	solve(root);
	for(int i=1;i<=m;i++)printf("%lld
",ans[i]);
	return 0;
}