Description：

给定一个标号为从 $1$ 到 $n$ 的、有 $m$ 条边的无向图，求边权最大值与最小值的差值最小的生成树。

$1\leqslant n\leqslant 50000,1\leqslant m\leqslant 200000$

Solution：

类似NOI2014魔法森林，先把边排序，然后求出来一个最小生成树，用 $LCT$ 维护，再枚举所有非树边，依次往里加，每次断掉一条树边，加一条非树边，然后用当前差值更新答案，注意最小值可以动态双指针，最大值维护一个变量 $cur$ 每次更新 $cur$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 250010

#define MAXM 200010

struct edges

{

	int u,v,w;

	bool tag;

}es[MAXM];

bool cmp_w(edges a,edges b){return a.w < b.w;}

struct node

{

	int c[2],fa,val,mv,pos;

	bool rev;

	node(){val = 0x3f3f3f3f;}

}t[MAXN];

inline bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

inline void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

inline int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

inline void maintain(int k)

{

	t[k].mv = t[k].val;t[k].pos = k;

	if(t[k].c[0] != 0 && t[t[k].c[0]].mv < t[k].mv)

	{

		t[k].mv = t[t[k].c[0]].mv;

		t[k].pos = t[t[k].c[0]].pos;

	}

	if(t[k].c[1] != 0 && t[t[k].c[1]].mv < t[k].mv)

	{

		t[k].mv = t[t[k].c[1]].mv;

		t[k].pos = t[t[k].c[1]].pos;

	}

	return;

}

inline void pushdown(int k)

{

	if(t[k].rev)

	{

		t[t[k].c[0]].rev ^= 1;t[t[k].c[1]].rev ^= 1;

		swap(t[k].c[0],t[k].c[1]);t[k].rev = false;

	}

	return;

}

inline void rotate(int x)

{

	register int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	maintain(y);maintain(x);

	return;

}

stack<int> s;

inline void splay(int x)

{

	s.push(x);

	for(register int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		register int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

inline void access(int k){for(register int i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;maintain(k);}return;}

inline void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

inline void link(int x,int y){makeroot(x);t[x].fa = y;return;}

inline void split(int x,int y){makeroot(x);access(y);splay(y);return;}

void cut(int x,int y){makeroot(x);access(y);splay(y);t[y].c[0] = t[x].fa = 0;maintain(y);return;}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= m;++i)

	{

		es[i].u = rd();es[i].v = rd();

		es[i].w = rd();

	}

	for(register int i = 1;i <= n;++i)

	{

		f[i] = i;t[i].pos = i;maintain(i);

	}

	sort(es + 1,es + 1 + m,cmp_w);

	register int ans = 0x3f3f3f3f;

	int cur = 0;

	for(register int i = 1;i <= m;++i)

	{

		if(es[i].u == es[i].v)continue; 

		t[i + n].val = es[i].w;t[i + n].pos = i + n;

		maintain(i + n);

		if(find(es[i].u) != find(es[i].v))

		{

			f[find(es[i].u)] = find(es[i].v);

			link(es[i].u,i + n);link(es[i].v,i + n);

			es[i].tag = true;

			cur = i;

		}

	}

	ans = (es[cur].w - es[1].w);

	for(register int i = 1,j = 1;i <= m;++i)

	{

		if(es[i].u == es[i].v)continue;

		if(!es[i].tag)

		{

			split(es[i].u,es[i].v);

			int p = t[es[i].v].pos - n;

			es[p].tag = false;

			cut(es[p].u,p + n);cut(es[p].v,p + n);

			link(es[i].u,i + n);link(es[i].v,i + n);

			es[i].tag = true;

			while(!es[j].tag)++j;

			cur = max(cur,i);

			if(es[cur].w - es[j].w < ans)

			{

				ans = es[cur].w - es[j].w;

			}

		}

	}

	cout << ans << endl;

	return 0;

}