萌新刚学LCT

39分

并不理解哪里出问题

去贴了贴之前写的板子

应该不是LCT的问题 如果是当我没说

#include<bits/stdc++.h>
using namespace std;
const int N=50020;
const int M=200020;
struct LCT
{
	int ch[2],rev,f,mx,val;
}a[M*2];
int stac[M*2];
struct edge
{
	int x,y,z;
}b[M*2];
bool cmp(edge a,edge b)
{
	return a.z>b.z;
}
bool vis[M*2];
#define ls a[x].ch[0]
#define rs a[x].ch[1]
bool isroot(int x)
{
	return !(a[a[x].f].ch[0]==x||a[a[x].f].ch[1]==x);
}
void update(int x)
{
	a[x].mx=a[x].val;
	if(b[a[x].mx].z<b[a[ls].mx].z)a[x].mx=a[ls].mx;
	if(b[a[x].mx].z<b[a[rs].mx].z)a[x].mx=a[rs].mx;
}
void pushrev(int x)
{
	swap(ls,rs);
	a[x].rev^=1;
}
void pushdown(int x)
{
	if(a[x].rev)
	{
		if(ls)pushrev(ls);
		if(rs)pushrev(rs);
		a[x].rev=0;
	}
}
void rotate(int x)
{
	int y=a[x].f;
	int z=a[y].f;
	int k=a[y].ch[1]==x;
	if(!isroot(y))a[z].ch[a[z].ch[1]==y]=x;	a[x].f=z;
	a[y].ch[k]=a[x].ch[k^1];	a[a[x].ch[k^1]].f=y;
	a[x].ch[k^1]=y;	a[y].f=x;
	update(y);update(x);
}
void splay(int x)
{
	int y=x,z=0;
	stac[++z]=y;
	while(!isroot(y))stac[++z]=y=a[y].f;
	while(z)pushdown(stac[z--]);
	while(!isroot(x))
	{
		y=a[x].f;z=a[y].f;
		if(!isroot(y))
			(a[y].ch[0]==x)^(a[z].ch[0]==y)?rotate(x):rotate(y);
		rotate(x);
	}	
	update(x);
}
void access(int x)
{
	for(int y=0;x;)
	{
		splay(x);
		rs=y;
		update(x);
		y=x;
		x=a[x].f;
	}
}
void makeroot(int x)
{
	access(x);
	splay(x);
	pushrev(x);
}
int findroot(int x)
{
	access(x);
	splay(x);
	while(ls)pushdown(x),x=ls;
	splay(x);
	return x;
}
void split(int x,int y)
{
	makeroot(x);
	access(y);
	splay(y);
}
void link(int x,int y)
{
	makeroot(x);
	if(findroot(y)!=x)a[x].f=y;
}
void cut(int x,int y)
{
	makeroot(x);
	if(findroot(y)==x&a[y].f==x&&a[y].ch[0]==0)
	{
		a[x].ch[1]=a[y].f=0;
		update(x);
	}
}
int n,m;
int ans=5000000;
bool check(int x,int y)
{	
	makeroot(x);
	return findroot(y)==x;
}
void solve()
{
	int tot=0,l=1;
	for(int i=1;i<=n;i++)
	{
		a[i].mx=a[i].val=0;
	}
	for(int i=1;i<=m;i++)
	{
		a[i+n].val=a[i+n].mx=i;
	}
	for(int i=1;i<=m;i++)
	{
		int x=b[i].x;
		int y=b[i].y;
		if(x==y)
		{
			vis[i]=1;
			continue;
		}
		if(!check(x,y))
		{
			link(x,i+n);link(i+n,y);tot++;
		}
		else
		{
			split(x,y);
			int temp=a[y].mx;
			cut(x,temp+n);cut(temp+n,y);
			vis[temp]=1;
			link(x,i+n);link(i+n,y);
		}
		while(vis[l]&&l<=i)
		{
			l++;
		}
		if(tot>=n-1)ans=min(ans,b[l].z-b[i].z);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].z);
	}
	sort(b+1,b+1+m,cmp);
	solve();
	printf("%d",ans);
	return 0;
}

/kk