题意

为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。

题解

因为他取的是两个东西分别的最大值
互不影响
如果两个一起做可能比较麻烦
所以不难想到，对于第一个先排序，然后按a值从小到大加边
这样就只需要让当前b最小就可以了
用LCT维护一下最小生成树即可
容易证明，对于一条路径上，如果又多条变的长度是一样的，并且里面要换掉一条，换哪一条都是一样的
然后就可以了
至于怎么保存边权，有一个小技巧，就是让边也变成一个点，就可以了

然后这题我发现了我lct模版的一个小问题，就是我的update是完全依赖于splay
但是如果x本来就是根了，那么他就不需要splay操作
我就会没有update，就GG
这个调了很久，下次要注意

CODE:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=150005;
const int M=200005;
int n,m;
struct qq{int x,y,a,b;}e[M];
int f[N];
int find (int x){
   return f[x]==x?f[x]:f[x]=find(f[x]);}
bool cmp (qq x,qq y){
   return x.a<y.a;}
struct qt
{int fa,son[2];int c,id;//最大的点权是什么，编号是什么bool rev;int c1,id1;//这个点权和边权
}tr[N];
void push_down (int x)
{if (!tr[x].rev) return ;int s1=tr[x].son[0],s2=tr[x].son[1];swap(tr[x].son[0],tr[x].son[1]);tr[s1].rev^=1;tr[s2].rev^=1;tr[x].rev^=1;
}
void update (int x)
{int s1=tr[x].son[0],s2=tr[x].son[1];int c=tr[x].c1,id=tr[x].id1;if (tr[s1].c>c) c=tr[s1].c,id=tr[s1].id;if (tr[s2].c>c) c=tr[s2].c,id=tr[s2].id;tr[x].c=c;tr[x].id=id;
}
bool is_root (int x)
{int fa=tr[x].fa;if (tr[fa].son[0]==x) return false;if (tr[fa].son[1]==x) return false;return true;
}
void pre (int x)
{if (!is_root(x)) pre(tr[x].fa);push_down(x);
}
void rotate (int x)
{int y=tr[x].fa,z=tr[y].fa,r,R;int w=(tr[y].son[0]==x);r=tr[x].son[w];R=y;tr[R].son[1-w]=r;if (r!=0) tr[r].fa=R;r=x;R=z;if (!is_root(y)){if (tr[R].son[0]==y) tr[R].son[0]=r;else tr[R].son[1]=r;}tr[r].fa=R;r=y;R=x;tr[R].son[w]=r;tr[r].fa=R;update(y);update(x);
}
void splay (int x)
{pre(x);update(x);while (!is_root(x)){int y=tr[x].fa,z=tr[y].fa;if (!is_root(y)){if ((tr[z].son[0]==y)==(tr[y].son[0]==x)) rotate(y);else rotate(x);}rotate(x);}
}
void access (int x)//使得x成为偏爱儿子 
{int last=0;while(x!=0){splay(x);tr[x].son[1]=last;last=x;x=tr[x].fa;}
}
void make_root(int x)
{access(x);splay(x);tr[x].rev^=1;
}
int find_root (int x)//寻找x这颗树的根 
{access(x);splay(x);while (tr[x].son[0]!=0) x=tr[x].son[0];return x;
}
void link (int x,int y)//连边 
{make_root(x);tr[x].fa=y;
}
void split (int x,int y)
{make_root(x);access(y);splay(y);
} 
void cut (int x,int y)//断边 
{split(x,y);tr[y].son[0]=tr[x].fa=0;update(y);
}
int main()
{int ans=5000000;scanf("%d%d",&n,&m);for (int u=1;u<=n;u++) {f[u]=u;tr[u].fa=tr[u].son[0]=tr[u].son[1]=tr[u].c=tr[u].id=0;tr[u].c1=tr[u].id1=0;tr[u].rev=false;}for (int u=1;u<=m;u++){scanf("%d%d%d%d",&e[u].x,&e[u].y,&e[u].a,&e[u].b);f[find(e[u].x)]=find(e[u].y);}if (find(1)!=find(n)) {printf("-1\n");return 0;}sort(e+1,e+1+m,cmp);for (int u=1;u<=m;u++){int x=e[u].x,y=e[u].y;tr[u+n].c=tr[u+n].c1=e[u].b;tr[u+n].id=tr[u+n].id1=u+n;if (find_root(x)!=find_root(y))//如果一开始就不在一个联通块，那么无脑连就可以了 {link(x,u+n);link(y,u+n);}else{split(x,y);int c=tr[y].c,id=tr[y].id;if (c>e[u].b)//如果比他大，那么替换 {int xx=e[id-n].x,yy=e[id-n].y;cut(xx,id);cut(id,yy);link(x,u+n);link(y,u+n);}}if (find_root(1)==find_root(n)){split(1,n);ans=min(ans,e[u].a+tr[n].c);}}printf("%d\n",ans);return 0;
}