[NOI2014]魔法森林

lct模板题。把所有的边按照a排个序，然后挨个加进去，然后以b为边权，求一个动态最小生成树。把每条边想成一个点，嵌在两个端点之间，然后每次加边的时候判一下新边的两个端点连不连通，连通的话就找两点路径上的权值最大的那个"边点"上的点权，把它和两端点cut了，然后再link这个"边点"和两个点。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
int ch[N][2],fa[N],mx[N],U[N],V[N],W[N],tot;
bool rev[N];
inline void pushup(int x) {
    mx[x]=x;
    if(W[mx[ch[x][0]]]>W[mx[x]]) mx[x]=mx[ch[x][0]];
    if(W[mx[ch[x][1]]]>W[mx[x]]) mx[x]=mx[ch[x][1]];
}
inline void pushdown(int x) {
    if(rev[x]) 
        swap(ch[x][0],ch[x][1]),
        rev[ch[x][1]]^=1,
        rev[ch[x][0]]^=1,
        rev[x]=0;
}
inline bool is_rt(int x) {
    return x!=ch[fa[x]][0]&&x!=ch[fa[x]][1];
}
inline bool ck(int x) {
    return x==ch[fa[x]][1];
}
inline void rotate(int x) {
    int f=fa[x],ff=fa[f];
    if(!is_rt(f)) ch[ff][ck(f)]=x;
    bool tag=ck(x);
    ch[f][tag]=ch[x][tag^1];
    fa[ch[f][tag]]=f;
    ch[x][tag^1]=f;
    fa[f]=x;
    fa[x]=ff;
    pushup(f);pushup(x);
}
int top,stk[N];
inline void splay(int x) {
    stk[top=1]=x;
    for(int i=x;!is_rt(i);i=fa[i]) stk[++top]=fa[i];
    while(top) pushdown(stk[top--]);
    for(int f;!is_rt(x);rotate(x)) 
        if(!is_rt(f=fa[x]))rotate(ck(x)==ck(f)?f:x);
}
inline void access(int x) {
    for(int t=0;x;t=x,x=fa[x]) 
        splay(x),ch[x][1]=t,pushup(x);
}
inline void makeroot(int x) {
    access(x);
    splay(x);
    rev[x]^=1;
}
inline int findroot(int x) {
    access(x);splay(x);
    while(ch[x][0]) x=ch[x][0];
    return x;
}
inline void link(int x,int y) {
    makeroot(x);
    fa[x]=y;
}
inline void cut(int x,int y) {
    makeroot(x);access(y);splay(y);
    ch[y][0]=fa[x]=0;
}
inline void connect(int x,int y,int v) {
    if(findroot(x)!=findroot(y)) {W[++tot]=v;U[tot]=x;V[tot]=y;link(U[tot],tot);link(V[tot],tot);return;}
    makeroot(x);access(y);splay(y);
    int a=mx[y];
    if(W[a]<=v) return;
    cut(a,U[a]);cut(a,V[a]);
    W[a]=v;
    link(U[a]=x,a);link(V[a]=y,a);
}
inline int query(int x,int y) {
    if(findroot(x)!=findroot(y)) return 19260817;
    makeroot(x);access(y);splay(y);
    return W[mx[y]];
}
int n,m;
struct Edge{int u,v,a,b;}e[N];
bool cmp(Edge x,Edge y) {
    return x.a<y.a;
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d%d",&e[i].u,&e[i].v,&e[i].a,&e[i].b);
    sort(e+1,e+1+m,cmp);
    tot=n;
    int ans=19260817;
    for(int i=1;i<=m;i++) {
        connect(e[i].u,e[i].v,e[i].b);
        ans=min(ans,query(1,n)+e[i].a);
    }
    if(ans==19260817) puts("-1");
    else cout<<ans;
}