【题解】Cf938G Shortest Path Queries

给出一个连通带权无向图,边有边权,要求支持 $q$ 个操作:

1 x y d 在原图中加入一条 $x$ 到 $y$ 权值为 $b$ 的边。

2 x y 把图中 $x$ 到 $y$ 的边删掉。

3 x y 表示询问 $x$ 到 $y$ 的异或最短路。

保证任意操作后原图连通无重边自环且操作均合法。

$1\leq n,m,q\leq 200000$

这题和 [HAOI2017] 的那个不是很相同。那题比较弱智,每次询问的只是包括 $1$ 的圈,但是这题需要维护连通性,并且没有初始边。所以就需要维护一个可撤销的 $dsu$ 来配合操作。

嗯,又写了一遍发现这个可撤销并查集的实现可能需要再领悟一下。

感觉代码实现方面还有很多需要熟悉的啊…尤其是线性基维护生成树、直接用 query(x) & query(y) 就可以直接求出询问,感觉很神奇。慢慢学、慢慢来吧。

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
#define gcr getchar
#define p_b push_back
#define mkp make_pair
#define pint pair<int,int>

const int B = 30 ;
const int N = 400010 ;
const int M = 800010 ;

struct edge{
int u, v, l, r, val ;
}e[M] ;
struct qss{
int u, v ;
}qs[N] ;
int cnt ;
int f[N] ;
int ans[N] ;
int n, m, q ;
int tot, cntq ;
int fa[N], sz[N] ;
map <pint, int> sch ;
vector <edge> S[N << 2] ;

struct xxj{
int base[50] ;
void Insert(int x){
//cout << x << endl;
for (int k = B ; ~k ; -- k)
if (1ll << k & x){
if (base[k]) x ^= base[k] ;
else return base[k] = x, void() ;
}
}
int Query(int x){
int ret = x ;
for (int i = B ; ~i ; -- i)
ret = min(ret, ret ^ base[i]) ;
return ret ;
}
}F ;
//using namespace xxj ;
void qr(int &x){
x = 0 ; char c = gcr() ;
while (c > '9' || c < '0') c = gcr() ;
while (isdigit(c)) x = x * 10 + c - 48, c = gcr() ;
}
void update(int rt, int l, int r, int ul, int ur, edge val){
if (ul > ur) return ;
if (ul <= l && r <= ur)
return S[rt].p_b(val), void() ;
int mid = (l + r) >> 1 ;
if (ul <= mid) update(rt << 1, l, mid, ul, ur, val) ;
if (ur > mid) update(rt << 1 | 1, mid + 1, r, ul, ur, val) ;
}
int dofa(int x){
while (x != fa[x])
x = fa[x] ; return x ;
}
int doxor(int x){
int ret = 0 ;
while (x != fa[x])
ret ^= f[x], x = fa[x] ;
return ret ;
}
void solve(int rt, int l, int r, xxj now){
vector <edge> O ; //O.clear() ;
int mid = (l + r) >> 1 ; bool flag = 0 ;
for (int i = 0 ; i < S[rt].size() ; ++ i){
int u = S[rt][i].u ;
int v = S[rt][i].v ;
int w = S[rt][i].val ;
int f1 = dofa(u), f2 = dofa(v) ;
//cout << u << " " << v << " " << w << endl ;
//cout << f1 << " " << f2 << " " << sz[f1] << " " << sz[f2] << endl ;
if (f1 != f2){
if (sz[f1] > sz[f2])
swap(f1, f2), swap(u, v) ;
O.p_b((edge){f1, f2, sz[f2]}) ;
fa[f1] = f2, sz[f2] += sz[f1],
f[f1] = doxor(u) ^ doxor(v) ^ w ;
}
else now.Insert(doxor(u) ^ doxor(v) ^ w) ;
}
if (l == r)
ans[l] = now.Query(doxor(qs[l].u) ^ doxor(qs[l].v)) ;
else solve(rt << 1, l, mid, now),
solve(rt << 1 | 1, mid + 1, r, now) ;
//for (int i = 1 ; i <= n ; ++ i) cout << f[i] << " " ; puts("") ;
for (int i = O.size() - 1 ; ~i ; -- i)
fa[O[i].u] = O[i].u, sz[O[i].v] = O[i].l, f[O[i].u] = 0 ;
}
int main(){
cin >> n >> m ;
int u, v, w, mk ;
for (int i = 1 ; i <= n ; ++ i)
fa[i] = i, sz[i] = 1 ;
for (int i = 1 ; i <= m ; ++ i){
qr(u), qr(v), qr(w) ;
e[++ tot] = (edge){u, v, 1, -1, w} ;
sch[mkp(u, v)] = tot ;
}
cin >> q ;
for (int i = 1 ; i <= q ; ++ i){
qr(mk), qr(u), qr(v) ;
if (u > v) swap(u, v) ;
if (mk == 1)
qr(w), ++ tot,
sch[mkp(u, v)] = tot,
e[tot] = (edge){u, v, cntq + 1, -1, w} ;
else if (mk == 2)
e[sch[mkp(u,v)]].r = cntq ;
else qs[++ cntq] = (qss){u, v} ;
}
for (int i = 1 ; i <= tot ; ++ i)
if (e[i].r < 0) e[i].r = cntq ;
// for (int i = 1 ; i <= tot ; ++ i)
// cout << e[i].l << " " << e[i].r << " " << e[i].u << " " << e[i].v << " " << e[i].val << endl ;
for (int i = 1 ; i <= tot ; ++ i)
update(1, 1, cntq, e[i].l, e[i].r, e[i]) ;
solve(1, 1, cntq, F) ;
for (int i = 1 ; i <= cntq ; ++ i)
printf("%d\n", ans[i]) ; return 0 ;
}