BZOJ 4568 幸运数字

发表于 | 更新于

Link

线性基学得和没学差不多。。

Solution

倍增维护线性基，需要特判起点和终点相等的情况。。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "lucida"
using std::fill;
using std::swap;
typedef unsigned long long qword;
const int MAXN=20000+11,MAXLOG=16;
int log_2[MAXN];
struct _{_(){
	log_2[0]=-1;
	for(int lg=1;lg<MAXN;++lg) {
		log_2[lg]=log_2[lg>>1]+1;
	}
}}Auto;
struct Edge {
	int to;Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXN<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t) {
	G[f]=new Edge(t,G[f]);
	G[t]=new Edge(f,G[t]);
}
struct Basis {
	qword a[62];
	Basis() {
		fill(a,a+62,0);
	}
	qword &operator [](const int &x) {
		return a[x];
	}
	const qword &operator [](const int &x) const {
		return a[x];
	}
	void Insert(qword x) {
		for(int lg=61;~lg;--lg) {
			if(x>>lg&1) {
				if(a[lg]) {
					x^=a[lg];
				} else {
					a[lg]=x;
					break;
				}
			}
		}
	}
	friend Basis Merge(Basis a,const Basis &b) {
		for(int lg=61;~lg;--lg) {
			if(b[lg]) {//超强的优化！
				a.Insert(b[lg]);
			}
		}
		return a;
	}
	qword Max() {
		qword res=0;
		for(int lg=61;~lg;--lg) {
			chkmx(res,res^a[lg]);
		}
		return res;
	}
};
qword a[MAXN];
int par[MAXN][MAXLOG],dep[MAXN],fa[MAXN];
Basis basis[MAXN][MAXLOG];
void DFS(int pos) {
	dep[pos]=dep[fa[pos]]+1;
	par[pos][0]=fa[pos];
	basis[pos][0].Insert(a[pos]);
	basis[pos][0].Insert(a[fa[pos]]);
	for(int lg=1;lg<=log_2[dep[pos]];++lg) {
		basis[pos][lg]=Merge(basis[pos][lg-1],basis[par[pos][lg-1]][lg-1]);
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	}
	for(Edge *e=G[pos];e;e=e->pre) {
		if(e->to!=fa[pos]) {
			int u=e->to;
			fa[u]=pos;
			DFS(u);
		}
	}
}
qword Query(int p1,int p2) {
	if(p1==p2) {
		return a[p1];
	} else {
		Basis b;
		if(dep[p1]<dep[p2]) {
			swap(p1,p2);
		}
		for(int len=dep[p1]-dep[p2],lg=log_2[len];~lg;--lg) {
			if(len>>lg&1) {
				b=Merge(b,basis[p1][lg]);
				p1=par[p1][lg];
			}
		}
		if(p1!=p2) {
			for(int lg=log_2[dep[p1]];~lg;--lg) {
				if(par[p1][lg]!=par[p2][lg]) {
					b=Merge(b,Merge(basis[p1][lg],basis[p2][lg]));
					p1=par[p1][lg];p2=par[p2][lg];
				}
			}
			b=Merge(b,Merge(basis[p1][0],basis[p2][0]));
		}
		return b.Max();
	}
}
int main() {
	freopen("input","r",stdin);
	freopen("output","w",stdout);
	int n,Q;is>>n>>Q;
	for(int i=1;i<=n;++i) {
		is>>a[i];
	}
	for(int i=1;i<=n-1;++i) {
		int x,y;is>>x>>y;
		Adde(x,y);
	}
	DFS(1);
	for(int i=1;i<=Q;++i) {
		int x,y;is>>x>>y;
		qword Ans=Query(x,y);
		os<<Ans<<'\n';
	}
	return 0;
}