题目大意 给一张带权无向图，无重边和自环，有如下操作： 删除某条边，保证这条边在删除前一定存在，并且不破坏原图连通性； 询问两点之间所有路径中最小权值的最大值是多少；
题解 问题的答案显然在原图的最小生成树上，于是本题就变成了动态维护删边最小生成树。 然而LinkCutTree维护最小生成树时并不支持删边操作，所以要离线处理，先删掉该删掉的边，再求最小生成树，把所有操作倒过来用LCT维护。
如何用LCT维护动态添边最小生成树 设原图中有n个点，m条边； 把每条边视为一个点，编号为，，权值为其边权，初始化边权最大值为自己的边权； 把原图中每个点的权值设成0； 求最小生成树，每添一条边时，设这条边连接x和y，这条边编号为k。直接把x和k连起来，y和k也连起来。
未完待续
Code
using namespace std;int n, m, q;struct edge{bool del;int id, x, y, w;edge(bool del = false, int id = 0, int x = 0, int y = 0, int w = 0) :id(id), x(x), y(y), w(w) {}}E[maxm];bool cmpw(const edge &a, const edge &b){return a.w < b.w;}bool cmpdic(const edge &a, const edge &b){return a.x < b.x || (a.x == b.x && a.y < b.y);}bool cmpid(const edge &a, const edge &b){return a.id < b.id;}struct node *T[maxm + maxn + maxn], *S[maxm + maxn + maxn];struct node{bool rev;int id, val;node *fa, *lc, *rc, *mx;node(bool rev = false, int id = 0, int val = 0,node *fa = nil, node *lc = nil, node *rc = nil, node *mx = nil): rev(rev), id(id), val(val),fa(fa), lc(lc), rc(rc), mx(mx) {}inline void update(){mx = this;if(lc -> mx -> val > mx -> val) mx = lc -> mx;if(rc -> mx -> val > mx -> val) mx = rc -> mx;}inline void pushdown(){if(rev){rev = false;lc -> rev ^= 1; rc -> rev ^= 1;swap(lc, rc);}}};void zig(node *x){node *y = x -> fa;y -> lc = x -> rc;x -> rc -> fa = y;x -> rc = y;x -> fa = y -> fa;if(y == y -> fa -> lc) y -> fa -> lc = x;else if(y == y -> fa -> rc) y -> fa -> rc = x;y -> fa = x;y -> update();}void zag(node *x){node *y = x -> fa;y -> rc = x -> lc;x -> lc -> fa = y;x -> lc = y;x -> fa = y -> fa;if(y == y -> fa -> lc) y -> fa -> lc = x;else if(y == y -> fa -> rc) y -> fa -> rc = x;y -> fa = x;y -> update();}void splay(node *x){int top = 0;S[top++] = x;for(node *i = x; i == i -> fa -> lc || i == i -> fa -> rc; i = i -> fa){S[top++] = i -> fa;}while(top–) S[top] -> pushdown();node *y = nil, *z = nil;while(x == x -> fa -> lc || x == x -> fa -> rc){y = x -> fa; z = y -> fa;if(x == y -> lc){if(y == z -> lc) zig(y);zig(x);}else{if(y == z -> rc) zag(y);zag(x);}}x -> update();}inline void access(node *x){for(node *y = nil; x != nil; y = x, x = x -> fa){splay(x);x -> rc = y;x -> update();}}inline void makeroot(node *x){access(x); splay(x); x -> rev ^= 1;}inline void lnk(node *x, node *y){makeroot(x);x -> fa = y;}inline void cut(node *x, node *y){makeroot(x);access(y); splay(y);x -> fa = y -> lc = nil;y -> update();}inline node* query(node *x, node *y){makeroot(x);access(y); splay(y);return y -> mx;}int ufs[maxn];inline int find(int x) { return x == ufs[x] ? x : find(ufs[x]); }int find(int x, int y){int l = 1, r = m, mid;while(l <= r){mid = l + r >> 1;if(E[mid].x < x || (E[mid].x == x && E[mid].y < y)) l = mid + 1;else if(E[mid].x == x && E[mid].y == y) return mid;else r = mid – 1;}}struct opt{int id, k, x, y, ans;opt(int id = 0, int k = 0, int x = 0, int y = 0, int ans = 0) :id(id), k(k), x(x), y(y), ans(ans) {}} sta[maxn];inline void read(int &a){char ch = getchar();a = 0;while(ch < ‘0’ || ch > ‘9’) ch = getchar();while(ch >= ‘0’ && ch <= ‘9’){a = a * 10 + ch – 48;ch = getchar();}}inline void write(int a){int top = 0, ch[30];do{ch[top++] = a % 10 + 48;a /= 10;} while(a > 0);while(top–) putchar(ch[top]);putchar(‘\n’);}void init(){#ifndef ONLINE_JUDGEfreopen(“2594i.txt”, “r”, stdin);freopen(“2594o.txt”, “w”, stdout);#endifint a, b, c;read(n); read(m); read(q);nil = new node(); *nil = node();for(int i = 1; i <= n + m + 100; ++i) T[i] = new node(false, i);for(int i = 1; i <= n; ++i) ufs[i] = i;for(int i = 1; i <= m; ++i){scanf(“%d%d%d”, &E[i].x, &E[i].y, &E[i].w);if(E[i].x > E[i].y) swap(E[i].x, E[i].y);}sort(E + 1, E + m + 1, cmpw);for(int i = 1; i <= m; ++i){E[i].id = i;T[n + i] -> val = E[i].w;T[n + i] -> mx = T[n + i];}sort(E + 1, E + m + 1, cmpdic);for(int i = 1; i <= q; ++i){read(sta[i].k); read(sta[i].x); read(sta[i].y);if(sta[i].k == 2){if(sta[i].x > sta[i].y) swap(sta[i].x, sta[i].y);int tmp = find(sta[i].x, sta[i].y);E[tmp].del = true; sta[i].id = E[tmp].id;}}sort(E + 1, E + m + 1, cmpid);}void work(){for(int i = 1, tot = 0; i <= m && tot < n – 1; ++i){if(!E[i].del){int tmpu = find(E[i].x), tmpv = find(E[i].y);if(tmpu != tmpv){ufs[tmpu] = tmpv;lnk(T[E[i].x], T[i + n]);lnk(T[E[i].y], T[i + n]);++tot;}}}for(int i = q; i > 0; –i){if(sta[i].k == 1){node *p = query(T[sta[i].x], T[sta[i].y]);sta[i].ans = p -> val;}else{node *p = query(T[sta[i].x], T[sta[i].y]);if(E[sta[i].id].w < p -> val){cut(T[E[p -> id – n].x], p);cut(T[E[p -> id – n].y], p);lnk(T[sta[i].x], T[sta[i].id + n]);lnk(T[sta[i].y], T[sta[i].id + n]);}}}for(int i = 1; i <= q; ++i) if(sta[i].k == 1){write(sta[i].ans);}for(int i = 0; i <= n + m + 100; ++i){delete T[i];T[i] = NULL;}}int main(){init();work();return 0;}
只有坚韧不拔向着目标奋进，成功后将在不远处等待着你的到来。
