感觉这题好强啊……本来以为能过，结果毫无疑问的被ge了一顿……在这里记录一下做的过程，也免得以后又忘记啦。
首先，我们应看出在这张图上，要让经过的水管最长的最短，就是要维护一棵动态的最小生成树。只是删除边不是很好操作，所以我们将删边改为加边，反向处理。如果发现新加的边可以更新最小生成树，我们就应该更新图，删去原图中最大的一条边。所以在LCT上我们要多维护一个信息，即当前最大的那条边是哪一条边。至此，大部分的难点都已解决，只是LCT维护的是点上的信息，而这道题的权值都在边上。我们将边转化成点，要将要链接的两个点分别与另一点相连，将信息存在另一个点上即可。
The road is tough and there's still a long way to go. Try your best and don't regret.
#include <bits/stdc++.h> using namespace std; #define maxn 150005 #define maxm 1500000 int n, m, opt[maxm], cnp, x[maxm], y[maxm]; int q[maxm], id, T[maxm]; int tot, ans[maxn], mark[maxn]; map <int, int> Map[maxn]; struct node { int fa, sum, rev; int id, v, ch[2]; }P[maxm]; struct edge { int u, v, t; friend bool operator <(edge a, edge b) { return a.t < b.t; } }E[maxn]; int read() { int x = 0, k = 1; char c; c = getchar(); while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); } while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * k; } void push_down(int x) { if(!P[x].rev) return; swap(P[x].ch[0], P[x].ch[1]); P[P[x].ch[0]].rev ^= 1, P[P[x].ch[1]].rev ^= 1; P[x].rev = 0; } void update(int x) { if(!x) return; P[x].id = x, P[x].sum = P[x].v; if(P[P[x].ch[0]].sum > P[x].sum) P[x].sum = P[P[x].ch[0]].sum, P[x].id = P[P[x].ch[0]].id; if(P[P[x].ch[1]].sum > P[x].sum) P[x].sum = P[P[x].ch[1]].sum, P[x].id = P[P[x].ch[1]].id; } bool is_root(int x) { return (P[P[x].fa].ch[0] != x) && (P[P[x].fa].ch[1] != x); } void rotate(int x) { int f = P[x].fa, gf = P[f].fa, k = P[f].ch[1] == x; if(!is_root(f)) P[gf].ch[P[gf].ch[1] == f] = x; P[x].fa = gf, P[f].fa = x; P[f].ch[k] = P[x].ch[k ^ 1], P[P[x].ch[k ^ 1]].fa = f; P[x].ch[k ^ 1] = f; update(f), update(x); } void Splay(int x) { int top = 1; q[top] = x; for(int i = x; !is_root(i); i = P[i].fa) q[++ top] = P[i].fa; for(int i = top; i; i --) push_down(q[i]); while(!is_root(x)) { int f = P[x].fa, gf = P[f].fa; if(!is_root(f)) (P[f].ch[1] == x) ^ (P[gf].ch[1] == f) ? rotate(x) : rotate(f); rotate(x); } update(x); } void Access(int x) { for(int ff = 0; x; ff = x, x = P[x].fa) { Splay(x); P[x].ch[1] = ff; update(x); } } void make_root(int x) { Access(x); Splay(x); P[x].rev ^= 1; } void Split(int u, int v) { make_root(u); Access(v); Splay(v); } void Link(int u, int v) { make_root(u); P[u].fa = v; } void Cut(int u, int v) { Split(u, v); P[v].ch[0] = P[u].fa = 0; } int Get_fa(int x) { Access(x); Splay(x); while(P[x].ch[0]) x = P[x].ch[0]; return x; } int main() { n = read(), m = read(); int q = read(); for(int i = 1; i <= m; i ++) { int u = read(), v = read(), w = read(); T[i] = w; E[++ cnp].u = u; E[cnp].v = v, E[cnp].t = w; } sort(E + 1, E + 1 + m); for(int i = 1; i <= m; i ++) Map[E[i].u][E[i].v] = Map[E[i].v][E[i].u] = i; for(int i = 1; i <= q; i ++) { opt[i] = read(); x[i] = read(); y[i] = read(); if(opt[i] == 2) mark[Map[x[i]][y[i]]] = 1; } for(int i = 1; i <= m; i ++) { int u = E[i].u, v = E[i].v, t = E[i].t; if(!mark[Map[u][v]] && Get_fa(u) != Get_fa(v)) { id = i + n, P[id].sum = P[id].v = t; Link(u, id), Link(id, v); } } for(int i = q; i; i --) { Split(x[i], y[i]); if(opt[i] == 1) // find a route ans[++ tot] = P[y[i]].sum; else // add edge { int now = n + Map[x[i]][y[i]]; int tem = E[now - n].t; if(tem < P[y[i]].sum) { P[now].v = tem; tem = P[y[i]].id; Cut(tem, E[tem - n].u); Cut(tem, E[tem - n].v); Link(now, x[i]), Link(now, y[i]); } } } for(int i = tot; i; i --) printf("%d ", ans[i]); return 0; }