loj2013 「SCOI2016」幸运数字

点分治+线性基

（为了这六个字窝调了一下午一晚上QAQ
#include <iostream>

#include <cstring>

#include <cstdio>

#include <vector>

#include <cassert>

using namespace std;

typedef long long ll;

int n, uu, vv, m, hea[20005], cnt, sze, rot, rnd[20005], siz[20005], bel[20005];

bool vis[20005];

ll a[20005], ans[200005];

struct Edge{

	int too, nxt;

}edge[40005];

struct Ques{

	int u, v, idx;

};

struct LinearBase{

	ll num[65];

	void clear(){

		memset(num, 0, sizeof(num));

	}

	void insert(ll x){

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

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

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

				else{

					num[i] = x;

					break;

				}

			}

	}

	ll operator+(const LinearBase &x)const{

		LinearBase c=x;

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

			c.insert(num[i]);

		ll re=0;

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

			if((re^c.num[i])>re)

				re ^= c.num[i];

		return re;

	}

}bas[20005];

vector<Ques> q[20005];

void add_edge(int fro, int too){

	edge[++cnt].nxt = hea[fro];

	edge[cnt].too = too;

	hea[fro] = cnt;

}

void getRoot(int x, int f){

	siz[x] = 1;

	rnd[x] = 0;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f && !vis[t]){

			getRoot(t, x);

			siz[x] += siz[t];

			rnd[x] = max(rnd[x], siz[t]);

		}

	}

	rnd[x] = max(rnd[x], sze-siz[x]);

	if(rnd[x]<rnd[rot])	rot = x;

}

void dfs1(int x, int f){

	bas[x].insert(a[x]);

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f && !vis[t]){

			bas[t] = bas[x];

			dfs1(t, x);

		}

	}

}

void dfs2(int x, int f, int fro){

	bel[x] = fro;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(t!=f && !vis[t])	dfs2(t, x, fro);

	}

}

void work(int x){

	vis[x] = true;

	bas[x].clear();

	dfs1(x, 0);

	bel[x] = x;

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t])		dfs2(t, x, t);

	}

	for(int i=0; i<q[x].size(); i++)

		if(q[x][i].u==x || q[x][i].v==x || bel[q[x][i].u]!=bel[q[x][i].v])

			ans[q[x][i].idx] = bas[q[x][i].u] + bas[q[x][i].v];

		else

			q[bel[q[x][i].u]].push_back(q[x][i]);

	q[x].clear();

	for(int i=hea[x]; i; i=edge[i].nxt){

		int t=edge[i].too;

		if(!vis[t]){

			rot = 0;

			sze = siz[t];

			getRoot(t, 0);

			q[rot] = q[t];

			if(rot!=t)	q[t].clear();

			work(rot);

		}

	}

}

int main(){

	cin>>n>>m;

	for(int i=1; i<=n; i++)	scanf("%lld", &a[i]);

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

		scanf("%d %d", &uu, &vv);

		add_edge(uu, vv);

		add_edge(vv, uu);

	}

	sze = n;

	rnd[0] = 0x3f3f3f3f;

	getRoot(1, 0);

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

		scanf("%d %d", &uu, &vv);

		if(uu==vv)	ans[i] = a[uu];

		else	q[rot].push_back((Ques){uu, vv, i});

	}

	work(rot);

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

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

	return 0;

}
巴特西

loj2013 「SCOI2016」幸运数字

最新文章

热门文章
