记得去年模拟赛的时候好像YY出二分答案枚举a,b的暴力，过了55欸
然后看正解，为了将两维变成一维，将a排序，模拟Kruskal的加边过程，同时维护1到n的最大值，加入一条边e(u,v,a,b)时有以下两种情况：
1） 若u,v已连通，则找出u->v上最大的b'，若b<b'，则替换之，同时更新答案，注意e一定经过1->n，因为去掉b'所在边时1,n一定不连通，若加上e后1,n连通，则必经过e，由于a是有序的，所以a是路径上最大的a，用a+MAX_b[1->n]更新答案即可。
2）否则，直接加入边e;
显然以上操作可以用lct处理。
对于维护边的信息，考虑把边看成点，与原来的真正的节点一起构成一棵（或多棵）lct，将边的信息存在对应的点上，并保证真正的结点不会对答案产生影响（相当于只起连通的作用），对于这道题，保证w[x]=0(x是结点的结点),x(x是边的结点）即可。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<algorithm> 5 #include<cstdio> 6 7 using namespace std; 8 9 // The default source begin----------- 10 const int MXD=~0u>>1; 11 const int D=15000000; 12 char in[D],out[300010*10],*I=in,*O=out; 13 #define gc (*I++) 14 #define pc(x) ((*O++)=x) 15 #define tQ template <typename Q> 16 tQ void gt(Q&x) { 17 static char c,f; 18 for(f=0;c=gc,!isdigit(c);)if(c=='-') f=1; 19 for(x=0;isdigit(c);c=gc) x=(x<<3) + (x<<1) +c-'0'; 20 f && (x=-x); 21 } 22 tQ void pt(Q x){ 23 static char stk[20]; 24 static int top; 25 top=0; 26 if(x==0) pc('0'); 27 for(;x;x/=10) stk[++top] = x%10+'0'; 28 for(;top;top--) pc(stk[top]); 29 } 30 // The default source end----------- 31 32 const int Maxn=50010,Maxm=100010; 33 int n,m; 34 struct Edge{ 35 int u,v,a,b; 36 inline bool operator < (const Edge&rhs) const { 37 return a<rhs.a || (a==rhs.a && b<rhs.b); 38 } 39 inline void read() { 40 gt(u),gt(v),gt(a),gt(b); 41 } 42 }edges[Maxm]; 43 44 int ch[Maxn+Maxm][2],p[Maxn+Maxm],flip[Maxn+Maxm],mx[Maxn+Maxm],w[Maxn+Maxm]; 45 46 #define l ch[x][0] 47 #define r ch[x][1] 48 void update(int x){ 49 if(!x) return; 50 mx[x]=x; 51 if(w[mx[l]]>w[mx[x]]) mx[x]=mx[l]; 52 if(w[mx[r]]>w[mx[x]]) mx[x]=mx[r]; 53 } 54 void down(int x) { 55 if(!x || !flip[x]) return; 56 swap(l,r); 57 flip[l]^=1; 58 flip[r]^=1; 59 flip[x]=0; 60 } 61 #undef l 62 #undef r 63 inline bool isroot(int x) { 64 return ch[p[x]][0]!=x && ch[p[x]][1]!=x; 65 } 66 inline void rotate(int x){ 67 int y=p[x],z=p[y]; 68 int l=ch[y][1]==x,r=l^1; 69 if(!isroot(y)){ 70 ch[z][ch[z][1]==y]=x; 71 } 72 p[y]=x; 73 p[ch[x][r]]=y; 74 p[x]=z; 75 76 ch[y][l]=ch[x][r]; 77 ch[x][r]=y; 78 79 update(y); 80 // update(x); 81 } 82 83 int stk[Maxn],top; 84 inline void splay(int x){ 85 stk[top=1]=x; 86 for(int t=x;!isroot(t);stk[++top]=t=p[t]); 87 for(;top;top--) down(stk[top]); 88 for(;!isroot(x);){ 89 int y=p[x],z=p[y]; 90 if(!isroot(y)) { 91 if( (ch[y][0]==x) ^ (ch[z][0]==y)) rotate(x); 92 else rotate(y); 93 } 94 rotate(x); 95 } 96 update(x); 97 } 98 99 inline void access(int x) { 100 for(int t=0;x;x=p[t=x]){ 101 splay(x); 102 ch[x][1]=t; 103 update(x); 104 } 105 } 106 107 inline void newroot(int x) { 108 access(x); 109 splay(x); 110 flip[x]^=1; 111 } 112 113 inline void n_as(int u,int v){ 114 newroot(u); 115 access(v); 116 splay(v); 117 } 118 119 inline void Cut(int x,int y) { 120 n_as(x,y); 121 ch[y][0]=p[x]=0; 122 update(x); 123 } 124 125 inline void Link(int x,int y) { 126 newroot(x); 127 p[x]=y; 128 } 129 130 int fa[Maxn]; 131 int Find(int x) { 132 return x==fa[x]?x:fa[x]=Find(fa[x]); 133 } 134 135 inline bool Union(int x,int y){ 136 x=Find(x);y=Find(y); 137 if(x==y) return 0; 138 return fa[x]=y,1; 139 } 140 141 inline void ufs_init(int n) { 142 for(int i=0;i<=n;i++) fa[i]=i; 143 } 144 145 inline void init() { 146 gt(n),gt(m); 147 for(int i=1;i<=m;i++) edges[i].read(); 148 ufs_init(n); 149 } 150 151 inline int getroot(int x) { 152 for(access(x),splay(x);ch[x][0];x=ch[x][0]); 153 return x; 154 } 155 156 inline void work() { 157 sort(edges+1,edges+m+1); 158 int ans=MXD; 159 for(int i=1;i<=m;i++) { 160 const Edge& e=edges[i]; 161 w[i+n]=e.b; 162 if(Union(e.u,e.v)) { 163 Link(e.u,i+n); 164 Link(e.v,i+n); 165 }else { 166 n_as(e.u,e.v); 167 int t=mx[e.v]; 168 if(w[t] > e.b) { 169 Cut(edges[t-n].u,t); 170 Cut(edges[t-n].v,t); 171 Link(e.u,i+n); 172 Link(e.v,i+n); 173 } 174 } 175 newroot(1); 176 if(getroot(n)==1) { 177 access(n); 178 splay(n); 179 ans = min (ans,e.a + w[mx[n]]); 180 } 181 } 182 printf("%d ",ans==MXD?-1:ans); 183 } 184 185 int main() { 186 #ifdef DEBUG 187 freopen("forest.in","r",stdin); 188 freopen("forest.out","w",stdout); 189 #endif 190 fread(in,1,D,stdin); 191 init(); 192 work(); 193 194 return 0; 195 }