[UOJ 3]【NOI2014】魔法森林：LCT

本文主要是介绍[UOJ 3]【NOI2014】魔法森林：LCT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击这里查看原题

将所有路径按a升序排序，用LCT维护路径上最大的b，将边权化为点权，如果加入一条边x，其两端点分别为u,v，那么将u与i+x连边，v与i+x连边。
如果(u,v)路径最大的b值大于当前边的b，那么删去b最大的边。
注意：access操作中必须pushup，因为这个调了好久

/*
User:Small
Language:C++
Problem No.:3
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 99999999
using namespace std;
const int M=200005;
int n,m,pre[M],fa[M],ch[M][2],val[M],mx[M],stk[M],ans=inf;
bool rev[M];
struct edge{int u,v,a,b;bool operator<(const edge &y)const{return a<y.a;}
}e[M];
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
bool get(int x){return ch[fa[x]][1]==x;
}
void pushup(int rt){int &l=ch[rt][0],&r=ch[rt][1];mx[rt]=rt;if(val[mx[l]]>val[mx[rt]]) mx[rt]=mx[l];if(val[mx[r]]>val[mx[rt]]) mx[rt]=mx[r];
}
void pushdown(int rt){int &l=ch[rt][0],&r=ch[rt][1];if(rev[rt]){rev[rt]^=1;rev[l]^=1;rev[r]^=1;swap(l,r);}
}
void rotate(int x){int y=fa[x],z=fa[y],side=get(x);if(!isroot(y)) ch[z][ch[z][1]==y]=x;fa[x]=z;ch[y][side]=ch[x][side^1];fa[ch[y][side]]=y;ch[x][side^1]=y;fa[y]=x;pushup(y);pushup(x); 
}
void splay(int x){int tp=0;stk[++tp]=x;for(int u=x;!isroot(u);u=fa[u]) stk[++tp]=fa[u];while(tp) pushdown(stk[tp--]);while(!isroot(x)){int y=fa[x];if(!isroot(y)) rotate(get(x)==get(y)?y:x);rotate(x);}
}
void access(int x){int t=0;for(int t=0;x;t=x,x=fa[x]){splay(x);ch[x][1]=t;pushup(x);}
}
void makeroot(int x){access(x);splay(x);rev[x]^=1;
}
void link(int x,int y){makeroot(x);fa[x]=y;splay(x);
}
void cut(int x,int y){makeroot(x);access(y);splay(y);fa[x]=ch[y][0]=0;
}
int query(int x,int y){makeroot(x);access(y);splay(y);return mx[y];
}
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);
}
int main(){freopen("data.in","r",stdin);//ios::sync_with_stdio(false);cin>>n>>m;for(int i=1;i<=n;i++) pre[i]=i;for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].a>>e[i].b;sort(e+1,e+m+1);for(int i=1;i<=m;i++){int u=e[i].u,v=e[i].v;if(find(u)==find(v)){int t=query(u,v);if(val[t]<=e[i].b) continue;cut(t,e[t-n].u);cut(t,e[t-n].v);}else pre[find(u)]=find(v);val[i+n]=e[i].b;mx[i+n]=i+n;link(u,i+n);link(v,i+n);if(find(1)==find(n)) ans=min(ans,e[i].a+val[query(1,n)]);}if(ans==inf) ans=-1;cout<<ans<<endl;return 0;
}