看心情填坑

终于调出了真正意义上的第一道LCT

所以说不要在意块状链表shi的弹飞绵羊

所以说不要在意并查集shi的洞穴勘测

所以说又要开始贴模板的没羞没臊的生活了

因为写access的时候只是看了定义然后自己yy的没有参考神犇的代码所以写得超级丑Orz，然后很多地方估计让R爷看了也是要被婊翻的。不过跑得好像还不错显然是R爷快啊Orz

我好像还不会写指针Orz

#include<cstdio>
#include<algorithm>
using namespace std;
struct tree{
    int l,r,xo,fa,s;
    bool re;
}t[300005];
int n,m,flag,x,y,fa[300005];
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
void pushdown(int root){
    if(t[root].re){
        swap(t[root].l,t[root].r);
        if(t[root].l)t[t[root].l].re^=true;
        if(t[root].r)t[t[root].r].re^=true;
        t[root].re=false;
    }
}
void pushup(int root){t[root].xo=t[t[root].l].xo^t[t[root].r].xo^t[root].s;}
void rorate(int k,int i){
    int tmp=t[k].fa;
    if(fa[tmp]){fa[k]=fa[tmp];fa[tmp]=0;}
    t[k].fa=t[tmp].fa;
    if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
    else t[t[tmp].fa].r=k;
    t[tmp].fa=k;
    if(i==0){
        if(t[k].l>0)t[t[k].l].fa=tmp;
        t[tmp].r=t[k].l;t[k].l=tmp;
    }else{
        if(t[k].r>0)t[t[k].r].fa=tmp;
        t[tmp].l=t[k].r;t[k].r=tmp;
    }
    pushup(tmp);pushup(k);
}
void splay(int k){
    while(t[k].fa){
        int tmp=t[k].fa;
        if(t[tmp].fa==0){
            pushdown(tmp);pushdown(k);
            if(t[tmp].r==k)rorate(k,0);
            else rorate(k,1);
        }
        else{
            int Tmp=t[tmp].fa;
            pushdown(Tmp);pushdown(tmp);pushdown(k);
            if(t[Tmp].l==tmp){
                if(t[tmp].l==k)rorate(tmp,1);
                else rorate(k,0);
                rorate(k,1);
            }else{
                if(t[tmp].r==k)rorate(tmp,0);
                else rorate(k,1);
                rorate(k,0);
            }
        }
    }
}
void access(int p){
    splay(p);
    pushdown(p);
    if(t[p].r){
        fa[t[p].r]=p;
        t[t[p].r].fa=0;t[p].r=0;
        pushup(p);
    }
    while(fa[p]){
        splay(fa[p]);
        pushdown(fa[p]);
        t[p].fa=fa[p];
        if(t[fa[p]].r){
            fa[t[fa[p]].r]=fa[p];
            t[t[fa[p]].r].fa=0;
        }
        t[fa[p]].r=p;
        fa[p]=0; 
        pushup(t[p].fa);
        splay(p);
    }
}
void change_root(int x){access(x);t[x].re^=1;}
void link(int x,int y){
    change_root(x);
    fa[x]=y;
}
void cut(int x,int y){change_root(x);access(y);if(t[y].l==x)t[y].l=t[x].fa=0,pushup(y);}
inline int find(int p){for(pushdown(p),access(p);t[p].l;p=t[p].l);return p;}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)t[i].s=t[i].xo=read();
    for(int i=1;i<=m;i++){
        flag=read();x=read();y=read();
        if(flag==0){
            change_root(x);            access(y);
            printf("%d\n",t[y].xo);
        }
        if(flag==1)if(find(x)!=find(y))link(x,y);
        if(flag==2)if(find(x)==find(y))cut(x,y);
        if(flag==3){
            t[x].s=y;
            while(x)pushup(x),x=t[x].fa;
        }
    }
}

--------------------------------------------------------------------------------------------------

#include<cstdio>
#include<algorithm>
using namespace std;
struct tree{
	int l,r,fa,max,w;
	bool re; 
}t[150005];
struct edge{
	int u,v,a,b;
}e[100005];
int ans,n,m,cnt;
inline int read(){
    int ret=0;
    char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline bool cmp(edge e1,edge e2){return e1.a<e2.a;}
void pushdown(int k){
	if(t[k].re){
		swap(t[k].l,t[k].r);
		if(t[k].l)t[t[k].l].re^=1;
		if(t[k].r)t[t[k].r].re^=1;
		t[k].re=false;
	}
}
void pushup(int k){
	t[k].max=k;
	if(t[k].l)if(t[t[t[k].l].max].w>t[t[k].max].w)t[k].max=t[t[k].l].max;
	if(t[k].r)if(t[t[t[k].r].max].w>t[t[k].max].w)t[k].max=t[t[k].r].max;
}
void rorate(int k,int i){
	int tmp=t[k].fa;
	t[k].fa=t[tmp].fa;
	if(t[t[tmp].fa].l==tmp)t[t[tmp].fa].l=k;
	if(t[t[tmp].fa].r==tmp)t[t[tmp].fa].r=k;
	t[tmp].fa=k;
	if(i==0){
		if(t[k].l)t[t[k].l].fa=tmp;
		t[tmp].r=t[k].l;t[k].l=tmp;
	}
	else{
		if(t[k].r)t[t[k].r].fa=tmp;
		t[tmp].l=t[k].r;t[k].r=tmp;
	}
	pushup(tmp);pushup(k);
}
void splay(int k){
	while((t[t[k].fa].l==k)||(t[t[k].fa].r==k)){
		int tmp=t[k].fa;
		if((t[t[tmp].fa].l!=tmp)&&(t[t[tmp].fa].r!=tmp)){
			pushdown(tmp);pushdown(k);
			if(t[tmp].l==k)rorate(k,1);
			else rorate(k,0);
		}else{
			int Tmp=t[tmp].fa;
			pushdown(Tmp);pushdown(tmp);pushdown(k);
			if(t[Tmp].l==tmp){
				if(t[tmp].l==k)rorate(tmp,1);
				else rorate(k,0);
				rorate(k,1);
			}else{
				if(t[tmp].r==k)rorate(tmp,0);
				else rorate(k,1);
				rorate(k,0);
			}
		}
	}
}
void access(int k){
	splay(k);pushdown(k);t[k].r=0;pushup(k);
	while(t[k].fa){
		splay(t[k].fa);
		pushdown(t[k].fa);
		t[t[k].fa].r=k;
		pushup(t[k].fa);
		splay(k); 
	}
}
void change_root(int x){access(x);t[x].re^=1;}
void cut(int x,int y){change_root(x);access(y);t[x].r=0;t[y].fa=0;pushup(x);}
void link(int x,int y){change_root(x);t[x].fa=y;}
inline int find(int k){access(k);while(t[k].l)k=t[k].l;return k;}
inline int qmax(int x,int y){change_root(x);access(y);return t[y].max;}
void Link(int x,int y,int w){
	cnt++;
	t[cnt].w=w;
	link(x,cnt);
	link(y,cnt);
}
void work(int x,int y){
	int k=qmax(x,y);change_root(k);
	access(x);splay(k);t[t[k].r].fa=0;t[k].r=0;
	access(y);splay(k);t[t[k].r].fa=0;t[k].r=0;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++)e[i].u=read(),e[i].v=read(),e[i].a=read(),e[i].b=read();
	sort(e+1,e+1+m,cmp);
	ans=2000000;
	cnt=n;
	for(int i=1;i<=m;i++){
		if(find(e[i].u)==find(e[i].v)){
			if(t[qmax(e[i].u,e[i].v)].w>e[i].b){
				work(e[i].u,e[i].v);
				Link(e[i].u,e[i].v,e[i].b);
			}
		}else Link(e[i].u,e[i].v,e[i].b);
		if(find(1)==find(n))ans=min(e[i].a+t[qmax(1,n)].w,ans);
	}
	if(ans==2000000)printf("-1");
	else printf("%d",ans);
}