感觉最近做的一些\(LCT\)的题目其实都是不断加边，判环，取较优者。
比如这道题，一句话题解就是按照边权\(A\)排序后用\(LCT\)维护边权\(B\)的最小生成树
比如，它用\(LCT\)实现的话主要就是遇到一条边后，若其联通了两个已经联通的点，那么其为返祖边，会形成环，那么我们就把环上最大的边断掉即可。
简单写就是\(split(u,v)\)，然后把\(cut(max, u), cut(max,v)\)
这道题也类似的，我们可以离线，将边按照边权\(A\)排序
然后不断的加边，如果一条边连接了两个联通块，那么这条路径是必需的。
这个时候我们保证了边权\(A\)单调递增，我们用\(LCT\)维护图中的边权\(B\)
然后对于一条路径，如果其沟通了两个已经联通的联通块，我们可以这样考虑：
当前路径的\(A\)比之前存在的任意路径的\(A\)都大，如果其\(B\)比这环上边\(B\)的最大值还要大，那么加入这条边只会让答案变得更不优。
如果当前路径的\(B\)比环上最大的\(B\)要小，那么加入这条路径后，显然有：
\((1):\)假如当前\(1-n\)未联通，那么对于后续的边，若其加入后可以使\(1-n\)联通，不难想到：其\(A\)显然仍然大于当前边，所以我们需要最小化链上的\(B\)，也就是断掉环上最大\(B\)的边，然后加入这条边
\((2):\)假如当前\(1-n\)已经联通，我们实际上已经求得了最大 A 比此边小的时候的答案，我们可以先加入此边，求出最大 A 稍微大一点的答案，取\(min\)，然后类似\((1)\)的分析，可以发现这条边加入后会使得后续边算得的答案更优。
当然前提是这条边的\(B\)大于环上最大\(B\)
注意细节
#includeusing namespace std;int read() { char cc = getchar(); int cn = 0, flus = 1; while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); } while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar(); return cn * flus;}#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )#define ls(x) t[x].son[0]#define rs(x) t[x].son[1]const int N = 150000 + 5; const int inf = 1234567890;struct E { int from, to, a, b;} e[N];struct LCT { int son[2], fa, mx, id; bool mark;} t[N];int n, m, Idnum, ans, w[N], st[N];bool cmp( E x, E y ) { return ( x.a == y.a ) ? x.b < y.b : x.a < y.a ;}bool isroot( int x ) { return ( ls(t[x].fa) != x ) && ( rs(t[x].fa) != x );}void pushup( int x ) { t[x].mx = w[x], t[x].id = x; if( ls(x) && t[ls(x)].mx > t[x].mx ) t[x].mx = t[ls(x)].mx, t[x].id = t[ls(x)].id; if( rs(x) && t[rs(x)].mx > t[x].mx ) t[x].mx = t[rs(x)].mx, t[x].id = t[rs(x)].id;}void rotate( int x ) { int f = t[x].fa, ff = t[f].fa, qwq = ( rs(f) == x ); t[x].fa = ff; if( !isroot(f) ) t[ff].son[rs(ff) == f] = x; t[f].son[qwq] = t[x].son[qwq ^ 1], t[t[x].son[qwq ^ 1]].fa = f; t[x].son[qwq ^ 1] = f, t[f].fa = x; pushup(f), pushup(x);}void pushmark( int x ) { if( t[x].mark ) { t[x].mark = 0, t[ls(x)].mark ^= 1, t[rs(x)].mark ^= 1, swap( ls(x), rs(x) ); }} void Splay( int x ) { int top = 0, now = x; st[++top] = now; while( !isroot(now) ) st[++top] = ( now = t[now].fa ); while( top ) pushmark( st[top--] ); while( !isroot(x) ) { int f = t[x].fa, ff = t[f].fa; if( !isroot(f) ) ( ( rs(ff) == f ) ^ ( rs(f) == x ) ) ? rotate(x) : rotate(f) ; rotate(x); }}void access( int x ) { for( int y = 0; x; y = x, x = t[y].fa ) Splay(x), t[x].son[1] = y, pushup(x);}void makeroot( int x ) { access(x), Splay(x), t[x].mark ^= 1, pushmark(x);}int findroot( int x ) { access(x), Splay(x), pushmark(x); while( ls(x) ) pushmark( x = ls(x) ); return x;}void split( int x, int y ) { makeroot(x), access(y), Splay(y);}void link( int x, int y ) { makeroot(x); if( findroot(y) != x ) t[x].fa = y;}bool check( int x, int y ) { makeroot(x); return findroot(y) != x;}signed main(){ n = read(), m = read(), ans = inf; rep( i, 1, m ) e[i].from = read(), e[i].to = read(), e[i].a = read(), e[i].b = read(); sort( e + 1, e + m + 1, cmp ); rep( i, 1, m ) { w[i + n] = e[i].b; if( e[i].from == e[i].to ) continue; if( check( e[i].from, e[i].to ) ) link( e[i].from, i + n ), link( i + n, e[i].to ); else { split( e[i].from, e[i].to ); int now = t[e[i].to].id, maxb = t[e[i].to].mx; if( maxb <= e[i].b ) continue; Splay( now ), t[ls(now)].fa = t[rs(now)].fa = 0; link( e[i].from, i + n ), link( i + n, e[i].to ); } if( !check( 1, n ) ) { split( 1, n ); ans = min( ans, t[n].mx + e[i].a ); } } if( ans == inf ) puts("-1"); else printf("%d\n", ans); return 0;}