题意

求最长边与最短边差值最小的生成树.

题解

LCT裸题.
将边按照边权从小到大排序,产生生成树的同时立即更新答案.
如果加入一条边的时候出现了环,把环上最小的边去掉加入该边.
每次跑最小值即可,用LCT可以较方便地维护.
为什么RE了啊啊啊啊啊啊啊啊啊!!!!!!!!!!!!!!!

#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){int x=0,f=1;char c=gc();for (;!isdigit(c);c=gc()) f^=c=='-';for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return f?x:-x;}
template <typename mitsuha>
inline bool read(mitsuha &x){x=0;int f=1;char c=gc();for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';if (!~c) return 0;for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');return x=f?x:-x,1;}
template <typename mitsuha>
inline int write(mitsuha x){if (!x) return 0&pc(48);if (x<0) x=-x,pc('-');int bit[20],i,p=0;for (;x;x/=10) bit[++p]=x%10;for (i=p;i;--i) pc(bit[i]+48);return 0;}
inline char fuhao(){char c=gc();for (;isspace(c);c=gc());return c;}
}using namespace chtholly;
using namespace std;
const int yuzu=4e5,inf=0x3f3f3f3f;
typedef int fuko[yuzu|10];
fuko vis;
struct edge{
int u,v,w;
void rd(){u=read(),v=read(),w=read();}
void wt(){printf("%d %d %d\n",u,v,w);}
bool operator <(const edge &b) const{return w<b.w;}
}e[yuzu|10];struct link_cut_tree{
fuko fa,ch[2],val,tag,xiao;
#define ls(x) ch[0][x]
#define rs(x) ch[1][x]
#define ws(x,y) (rs(x)==y)
int nrt(int x){return ls(fa[x])==x||rs(fa[x])==x;}
void rev(int x){swap(ls(x),rs(x)),tag[x]^=1;}
void push_down(int x){if (tag[x]) rev(ls(x)),rev(rs(x)),tag[x]=0;} 
void pushall(int x){if (nrt(x)) pushall(fa[x]); push_down(x);} 
void push_up(int x){xiao[x]=val[x];if (e[xiao[ls(x)]].w<e[xiao[x]].w) xiao[x]=xiao[ls(x)];if (e[xiao[rs(x)]].w<e[xiao[x]].w) xiao[x]=xiao[rs(x)];}
void zhuan(int x){int y=fa[x],z=fa[y],k=ws(y,x),ps=ch[!k][x];if (nrt(y)) ch[ws(z,y)][z]=x;ch[k][y]=ps,ch[!k][x]=y;if (ps) fa[ps]=y;fa[x]=z,fa[y]=x,push_up(y);}
void splay(int x){pushall(x);for (;nrt(x);zhuan(x)){int y=fa[x],z=fa[y];if (nrt(y)) zhuan(ws(z,y)^ws(y,x)?x:y);}push_up(x);}
void access(int x){for (int y=0;x;y=x,x=fa[x]) splay(x),rs(x)=y,push_up(x);}
void mkrt(int x){access(x),splay(x),rev(x);}
void split(int x,int y){mkrt(x),access(y),splay(y);}
int fdrt(int x){access(x),splay(x);for (;ls(x);x=ls(x)) push_down(x);return x;}
int link(int x,int y){mkrt(x),fa[x]=y;}
int cut(int x,int y){split(x,y),fa[x]=ls(y)=0,push_up(y);}
}my_;
#define val my_.val
#define xiao my_.xiao
#define access my_.access
#define split my_.split
#define mkrt my_.mkrt
#define splay my_.splay
#define link my_.link
#define cut my_.cut
#define fdrt my_.fdrt
int main(){
int i,n=read(),m=read(),llx=inf;
for (i=1;i<=m;++i) e[i].rd();
e[0].w=inf,sort(e+1,e+m+1);
int cnt=0,k=1;
for (i=0;i<=n+m;++i) val[i]=i<=n?0:i-n;
for (i=1;i<=m;++i){int u=e[i].u,v=e[i].v,w=e[i].w;if (u^v){if (fdrt(u)==fdrt(v)){split(u,v);int id=xiao[v];vis[id]=0;cut(e[id].u,id+n),cut(id+n,e[id].v),--cnt;} link(u,i+n),link(i+n,v),++cnt;vis[i]=1;}if (cnt>=n-1){for (;!vis[k];++k);llx=min(llx,w-e[k].w);} }
write(llx);
}

谢谢大家.