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;
}