【BZOJ3669】【NOI2014】—魔法森林（LCT维护最小生成树）

传送门

把$a$排序，此时我们所关注的就是1~n路径上$b$的最大值

考虑维护一个$b$的最小生成树，实际上就是连了一条边之后找到路径上的最大值看是否更优
更新一下答案就是了

注意$Lct$无法维护边权
要把边变成点

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();
	return res*f;
} 
const int N=150005;
int a[N];
#define lc(u) son[u][0]
#define rc(u) son[u][1]
namespace Lct{
	int q[N],son[N][2],rev[N],fa[N],mx[N];
	inline bool isrc(int u){
		return rc(fa[u])==u;
	}
	inline bool isrt(int u){
		if(!fa[u])return 1;
		return lc(fa[u])!=u&&rc(fa[u])!=u;
	}
	inline void pushup(int u){
		mx[u]=u;
		if(a[mx[lc(u)]]>a[mx[u]])mx[u]=mx[lc(u)];
		if(a[mx[rc(u)]]>a[mx[u]])mx[u]=mx[rc(u)];
	}
	inline void pushdown(int u){
		if(!rev[u])return;
		swap(lc(u),rc(u));		
		if(lc(u))rev[lc(u)]^=1;
		if(rc(u))rev[rc(u)]^=1;
		rev[u]=0;
	}
	inline void rotate(int v){
		int u=fa[v],z=fa[u];
		int t=rc(u)==v;
		if(!isrt(u))son[z][rc(z)==u]=v;
		fa[v]=z;
		son[u][t]=son[v][t^1],fa[son[v][t^1]]=u;
		son[v][t^1]=u,fa[u]=v;
		pushup(u),pushup(v);
	}
	inline void splay(int u){
		q[q[0]=1]=u;
		for(int v=u;!isrt(v);v=fa[v])q[++q[0]]=fa[v];
		for(int i=q[0];i;i--)pushdown(q[i]);
		while(!isrt(u)){
			if(!isrt(fa[u])){
				if(isrc(u)==isrc(fa[u]))rotate(fa[u]);
				else rotate(u);
			}
			rotate(u);
		}
		pushup(u);
	}
	inline void access(int u){
		for(int v=0;u;v=u,u=fa[u]){
			splay(u),rc(u)=v;
			if(v)fa[v]=u;
			pushup(u);
		}
	}
	inline int findrt(int u){
		access(u),splay(u);
		while(pushdown(u),lc(u))u=lc(u);
		splay(u);return u;
	}
	inline void makert(int u){
		access(u),splay(u),rev[u]^=1;
	}
	inline void link(int u,int v){
		makert(u),fa[u]=v;
	}
	inline void cut(int u,int v){
		makert(u),access(v),splay(v);
		lc(v)=fa[u]=0,pushup(v);
	}
	inline int query(int u,int v){
		makert(u),access(v),splay(v);return mx[v];
	}
}
using namespace Lct;
struct edge{
	int u,v,a,b;
}e[N];
inline bool comp(const edge &a,const edge &b){
	return a.a==b.a?a.b<b.b:a.a<b.a;
}
int f[N];
int n,m;
inline int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
	n=read(),m=read();int ans=1e9;
	for(int i=1;i<=m;i++){
		e[i].u=read(),e[i].v=read();
		e[i].a=read(),e[i].b=read();
	}
	for(int i=1;i<=n;i++)f[i]=i;
	sort(e+1,e+m+1,comp);
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v;
		int f1=find(u),f2=find(v);
		if(f1==f2){
			int k=query(u,v);
			if(a[k]<=e[i].b)continue;
			cut(k,e[k-n].u),cut(k,e[k-n].v);
		}
		else f[f1]=f2;
		a[n+i]=e[i].b,mx[n+i]=n+i;
		link(u,n+i),link(v,n+i);
		if(find(1)==find(n))ans=min(ans,e[i].a+a[query(1,n)]);
	}
	if(ans==1e9)ans=-1;
	cout<<ans;
}