Problem

给定一张无向边权图,要求维护三个操作

OP1.$[x,y,z]$:在点$x$和点$y$之间加一条边权为z的边,保证之前没有边

OP2.$[x,y]$:将点$x$和$y$之间的边删除,保证之前有边

OP3.$[x,y]$:查询$x$到$y$的路径的异或最小值,可以是非简单路

Solution

图上两点异或路径的最小值为生成树上异或距离和树上环的组合

我们以OP3为时间线建线段树,将覆盖操作时间点的边保存在线段树节点

对OP3的线段树进行DFS遍历,用并查集维护两点间的$xor$距离

当成环时将环加入$xor$线性基,在叶节点查询$xor$线性基和$xor$距离组合的最小值即可

线性基空间$O(30)$可以选择直接传参,并查集空间$O(n)$需回溯

时间复杂度$O(mlog_2t)$,$t$为OP3的数量,$m$为总边数

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 <bits/stdc++.h>
using namespace std;
const int N = 400000 + 10;
using PII = pair<int, int>;
// Xor Base
struct Base {
int p[31];
void ins(int x) {
for (int j = 30; ~j; --j)
if ((x >> j) & 1) {
if (!p[j]) {
p[j] = x;
return;
}
x ^= p[j];
}
}
int ask(int x) {
for (int j = 30; ~j; --j) x = min(x, x ^ p[j]);
return x;
}
} S;
// Union Find Set
int st[N << 1], top, f[N], val[N], d[N];
void init(int n) {
for (int i = 1; i <= n; i++) f[i] = i, val[i] = 0, d[i] = 1;
top = 0;
}
int sf(int x) { return f[x] == x ? x : sf(f[x]); }
int ask(int x) {
int res = 0;
for (; x != f[x]; x = f[x]) res ^= val[x];
return res;
}
void back(int tag) {
for (; top != tag; top--) {
if (st[top] < 0)
d[-st[top]]--;
else {
f[st[top]] = st[top];
val[st[top]] = 0;
}
}
}
void Union(int x, int y, int _val) {
if (d[x] > d[y]) swap(x, y);
if (d[x] == d[y]) d[y]++, st[++top] = -y;
f[x] = y;
val[x] = _val;
st[++top] = x;
}
// Edge
struct data1 {
int x, y, w, l, r;
} E[N];
// Query
struct data2 {
int x, y;
} Q[N];
// Segment Tree
vector<int> v[N << 1];
int idx(int l, int r) { return l + r | l != r; }
void upd(int l, int r, int y) {
int x = idx(l, r), mid = (l + r) >> 1;
if (E[y].l <= l && r <= E[y].r) {
v[x].push_back(y);
return;
}
if (E[y].l <= mid) upd(l, mid, y);
if (E[y].r > mid) upd(mid + 1, r, y);
}
void dfs(int l, int r, Base S) {
int x = idx(l, r), t = top, mid = (l + r) >> 1;
for (auto y : v[x]) {
int fx = sf(E[y].x), fy = sf(E[y].y);
int dx = ask(E[y].x), dy = ask(E[y].y);
if (fx == fy) {
S.ins(dx ^ dy ^ E[y].w);
continue;
}
Union(fx, fy, dx ^ dy ^ E[y].w);
}
if (l == r) {
int dx = ask(Q[l].x), dy = ask(Q[l].y);
printf("%d\n", S.ask(dx ^ dy));
back(t);
return;
}
dfs(l, mid, S);
dfs(mid + 1, r, S);
back(t);
}
map<PII, int> id;
int n, m, x, y, z, q, op, tot;
int main() {
scanf("%d%d", &n, &m);
init(n);
tot = 0;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
if (x > y) swap(x, y);
E[i] = {x, y, z, tot + 1, -1};
id[{x, y}] = i;
}
scanf("%d", &q);
while (q--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d%d%d", &x, &y, &z);
if (x > y) swap(x, y);
E[++m] = {x, y, z, tot + 1, -1};
id[{x, y}] = m;
} else if (op == 2) {
scanf("%d%d", &x, &y);
if (x > y) swap(x, y);
E[id[{x, y}]].r = tot;
} else {
scanf("%d%d", &x, &y);
Q[++tot] = {x, y};
}
}
for (int i = 1; i <= m; i++) {
if (E[i].r == -1) E[i].r = tot;
if (E[i].l <= E[i].r) upd(1, tot, i);
}
dfs(1, tot, S);
return 0;
}