「NOIP模拟赛」最短路 【线性基】

线性基插入+查询

最短路

时间限制:3s\mathtt{s} 空间限制:512MB\mathtt{MB}

题目描述

小W有一棵 nn 个点的带权树,现在他想从 SS 走到 TT定义一条路径的长度为上面所有边的长度的异或和

但是他觉得直接沿着树上的边走太慢了,于是他决定新建一些边。他有 mm 个修建计划,第 ii 个是在 uuvv 之间修建一条长为 ww 的边。

现在他有一些询问,每个询问形如 S,T,l,rS, T, l, r,表示如果动用 [l,r][l,r] 区间内的所有修建计划,他从 SS 走到 TT 的最短路长度应该是多少。

输入格式

第一行三个整数 nnmmqq

接下来 n1n-1 行,每行三个整数 uuvvww,表示原本树上有一条 uuvv 之间有一条长度为 ww 的边。

接下来 mm 行,第 ii 行有三个整数 uuvvww,表示一个修建计划。

接下来 qq 行,每行四个整数 SSTTllrr,表示一组询问。

输出格式

输出共 qq 行,表示每组询问的答案。

样例输入

1
2
3
4
5
6
7
8
9
10
11
4 4 3
1 2 1
2 3 2
3 4 3
1 2 2
2 3 3
3 4 1
1 3 1
1 4 1 1
1 2 1 3
3 4 3 3

样例输出

1
2
3
0
0
1

数据规模与约定

对于 20%20\% 的数据,n,m,q1000n, m, q \le 1000

对于 50%50\% 的数据,

对于 100%100\% 的数据,

提示

输入输出量可能很大,请使用较快的I/O方式。

Solution

离线询问操作。

先处理出 S,TS,T 间在树上走的代价。修建计划影响的代价用线性基维护。 考虑从小到大枚举询问的右端点 rr ,如果左端点 ll 从大到小,那么就可以利用上一次线性基的结果更新答案。

于是我们可以将不在范围内的元素删除,动态维护线性基即可。

时间复杂度 O(m log w)O(m~log~w)

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
#include <bits/stdc++.h>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}

int cnt, nxt[600005], head[300005], to[600005], w[600005];

int s[300005];
void dfs(int u, int fa=0) {
for(int i=head[u];i;i=nxt[i])if(to[i]!=fa)
s[to[i]]=s[u]^w[i], dfs(to[i], u);
}

int b[32], k[32];
void insert(int num, int x) {
for(int i=30;~i;--i)if(x&1<<i) {
if(!b[i]) {b[i]=x,k[i]=num;break;}

if(k[i]<num)
swap(num, k[i]), swap(x, b[i]);
x^=b[i];
}
}

int n, m, q, a[300005], p[300005], l[300005];

int main() {
n=read(), m=read(), q=read();
int u, v;
rep(i,2,n) {
u=read(), v=read();
nxt[++cnt]=head[u], to[head[u]=cnt]=v;
nxt[++cnt]=head[v], to[head[v]=cnt]=u;
w[cnt]=w[cnt-1]=read();
}
dfs(1);
memset(head, 0, sizeof head);
rep(i,1,m) a[i]=s[read()]^s[read()]^read();
rep(i,1,q) {
p[i] = s[read()]^s[read()];
l[i]=read(), u=read();
nxt[i]=head[u], head[u]=i;
}

rep(r,1,m) {
insert(r, a[r]);
for(int z=head[r];z;z=nxt[z])
for(int i=30;~i;--i)if(k[i]>=l[z])
p[z]=min(p[z], p[z]^b[i]);
}
rep(i,1,q) printf("%d\n", p[i]);
return 0;
}