SCOI2016Day1 第二道

题目链接

题目大意

每个点上有一个权值,多次查询一条路径每个点任意选

解题报告

首先,每个点任意选或不选的最大异或和是线性基的裸题,所以考虑将一条路径的线性基合并;

这个显然可以使用动态点分治完成, 记录每个点到点分树上的每个祖先的路径线性基(空间复杂度\(O(n\log{n}\log{X})\)), 预处理的时间是\(O(n\log{n}\log{X})\), 查询的时候通过\(O(\log{n})\)确定路径在点分树上的lca, 然后在lca(也就是一个重心处)将两个线性基合并, 复杂度是\(O(q\times(\log{n}+\log^2{p}))\) .

然而我却使用了一个复杂度非常烂的算法(写的时候以为是一样的。。。) , 倍增+线性基合并。

首先预处理的时候需要做\(O(n\log{n}\log^2{X})\), 因为线性基的合并是\(O(\log^2{P})\)的。

查询的时候我更加愚蠢的跳了\(\log{n}\)次, 每次都合并了线性基。。所以复杂度是\(O(q\times\log{n}\log^2{X})\) .

然后竟然还过了。。艹?

代码

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
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
#define W(x,w) (((x)>>w)&1)
typedef long long ll;
const int N=20010;
struct base {
int c; ll a[65]; base() {memset(a,0,sizeof(a)),c=0;};
void ins(ll x) {
vep(i,60,0) if (W(x,i)) {
if (!a[i]) { ++c,a[i]=x; break;}
else { x^=a[i]; if (!x) break;}
}
}
void print() {
cout<<c<<":"<<endl;
vep(i,60,0) if (a[i]) cout<<i<<":"<<a[i]<<endl;
cout<<endl;
}
} b[N][16];
struct edge {
int nxt,to; edge(int nxt=0,int to=0)
:nxt(nxt),to(to) {}
} e[N<<1];
int n,q,hed[N],f[N][16],tot,de[N]; ll g[N];
template <typename T> inline void in(T &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
inline void add(int x,int y) {
e[++tot]=edge(hed[x],y),hed[x]=tot;
}
base merge(base x, base y) {
if (x.c>y.c) swap(x,y);
xep(i, 61) if (x.a[i]) y.ins(x.a[i]);
return y;
}
void build(int x) {
b[x][0].ins(g[x]); de[x]=de[f[x][0]]+1;
for (int i=0;f[x][i];++i) {
f[x][i+1]=f[f[x][i]][i];
b[x][i+1]=merge(b[x][i],b[f[x][i]][i]);
}
int y;
for (int i=hed[x];i;i=e[i].nxt)
if (y=e[i].to, y!=f[x][0])
f[y][0]=x,build(y);
}
inline void query(int x,int y) {
if (de[x]<de[y]) swap(x,y);
base as; int dta=de[x]-de[y];
vep(i,14,0) if (W(dta,i))
as=merge(as, b[x][i]), x=f[x][i];
if (x!=y) {
vep(i,14,0) if (f[x][i]!=f[y][i]) {
as=merge(as, b[x][i]), as=merge(as, b[y][i]);
x=f[x][i], y=f[y][i];
}
as=merge(as,b[x][0]), as=merge(as,b[y][0]);
x=f[x][0], y=f[y][0];
}
as=merge(as,b[x][0]);
ll ans=0;
vep(i,60,0) if ((ans^as.a[i])>ans)
ans=ans^as.a[i];
printf("%lld\n", ans);
}
int main() {
in(n), in(q); rep(i,1,n) in(g[i]); int x,y;
xep(i,n-1) in(x),in(y),add(x,y),add(y,x);
build(1);
xep(i,q) { in(x),in(y); query(x,y);}
return 0;
}

留言