题解 P4172 【[WC2006]水管局长】
Nemlit
2019-03-22 10:16:53
## [原文地址](https://www.cnblogs.com/bcoier/p/10576550.html)
### 题目大意：
给定一张图，支持删边，求两点的路径中所有权值的最大值的最小值，~~貌似很绕的样子~~
由于有删边，不难想到$LCT$，又因为$LCT$不支持维护图，而且只有删边操作，于是我们考虑时间回溯。
把这道题变成模板有几个问题：
（思路为个人$YY$，可能非常麻烦）
### $1.$我们怎么确定最后的状态呢？
首先我们先用$map$存每一条边，在询问操作时，每删一条边，就把他在$map$上去掉，最后剩下的边即为最终状态
### $2.$加边的时候会出现环该怎么办呢？
要让答案更优，我们显然要动态维护[最小生成树](https://www.luogu.org/blog/Hakuryu/solution-p3366)，然后维护了最小生成树后就只要找最小生成树树上两点的最大值了
附上常数极大又十分丑陋的代码：
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define drep(i, s, t) for(re int i = t; i >= s; -- i)
#define updown(x) swap(ch[1][x], ch[0][x]), tag[x] ^= 1
#define get_fa(x) ch[1][fa[x]] == x
#define isroot(x) ch[1][fa[x]] == x || ch[0][fa[x]] == x
#define _ 150006
int n, m, Q, ans[_], Top, st[_], top, fa[_], tag[_], ch[2][_], val[_], ma[_], id[_];
struct node {int opt, u, v, w;}e[_];
pair<int, int> a[_];
map<pair<int, int>, int> q, Id;
il void pushdown(int x) {
if(!tag[x]) return;
if(ch[1][x]) updown(ch[1][x]);
if(ch[0][x]) updown(ch[0][x]);
tag[x] = 0;
}
il void pushup(int x) {
ma[x] = val[x], id[x] = x;
if(ch[1][x] && ma[x] < ma[ch[1][x]]) ma[x] = ma[ch[1][x]], id[x] = id[ch[1][x]];
if(ch[0][x] && ma[x] < ma[ch[0][x]]) ma[x] = ma[ch[0][x]], id[x] = id[ch[0][x]];
}
il void rotate(int x) {
int y = fa[x], z = fa[y], w = get_fa(x), k = get_fa(y);
ch[w][y] = ch[w ^ 1][x], fa[ch[w ^ 1][x]] = y;
if(isroot(y)) ch[k][z] = x; fa[x] = z;
ch[w ^ 1][x] = y, fa[y] = x;
pushup(y), pushup(x);
}
il void Splay(int x) {
int y = x;
st[++ top] = x;
while(isroot(y)) st[++ top] = y = fa[y];
while(top) pushdown(st[top --]);
while(isroot(x)) {
int y = fa[x];
if(isroot(y)) rotate(get_fa(x) == get_fa(y) ? y : x);
rotate(x);
}
}
il void access(int x) {for(int y = 0; x; x = fa[y = x]) Splay(x), ch[1][x] = y, pushup(x);}
il void makeroot(int x) {access(x), Splay(x), updown(x);}
il int findroot(int x) {
access(x), Splay(x);
while(ch[0][x]) x = ch[0][x];
Splay(x);
return x;
}
il void spilt(int x, int y) {makeroot(x), access(y), Splay(y);}
il void link(int x, int y) {
makeroot(x);
if(findroot(y) != x) fa[x] = y;
}
int main() {
file(a);
n = read(), m = read(), Q = read();
rep(i, 1, m) {
int u = read(), v = read();
a[i] = make_pair(u, v), q[make_pair(v, u)] = q[a[i]] = read(), val[i + n] = q[a[i]];
Id[a[i]] = Id[make_pair(v, u)] = i;
}
rep(i, 1, Q) {
int opt = read(), u = read(), v = read();
e[i] = (node){opt, u, v, q[make_pair(u, v)]};
}
rep(i, 1, Q)
if(e[i].opt == 2) q[make_pair(e[i].u, e[i].v)] = q[make_pair(e[i].v, e[i].u)] = 0;
rep(i, 1, m) {
if(q[a[i]] == 0) continue;
if(findroot(a[i].first) == findroot(a[i].second)) {
spilt(a[i].first, a[i].second); int now = id[a[i].second];
if(val[i + n] >= val[now]) continue;
Splay(now), fa[ch[1][now]] = fa[ch[0][now]] = 0;
}
link(a[i].first, i + n), link(i + n, a[i].second);
}
drep(i, 1, Q) {
int u = e[i].u, v = e[i].v;
if(e[i].opt == 2) {
if(findroot(u) == findroot(v)) {
spilt(u, v); int now = id[v];
if(e[i].w >= val[now]) continue;
Splay(now), fa[ch[1][now]] = fa[ch[0][now]] = 0;
}
link(u, Id[make_pair(u, v)] + n), link(Id[make_pair(u, v)] + n, v);
}
else spilt(u, v), ans[++ Top] = val[id[v]];
}
drep(i, 1, Top) printf("%d\n", ans[i]);
return 0;
}
```