题目链接
先将边排序，这样就可以按从小到大的顺序维护生成树，枚举到一条未连通的边就连上，已连通则(用当前更大的)替换掉路径上最小的边，这样一定不会更差。
每次构成树时更新答案。答案就是当前边减去生成树上最小边的权值。
LCT上维护最小边的编号。求最小边把树上的边用vis[]标记即可。
不熟啊.
(另外暴力可以排序后枚举一个分界点，在它之后求最小生成树，在它之前求最大生成树)
#include
#include
#include
#define gc() getchar()
#define INF 10000007
const int N=5e4+5,M=2e5+5,S=N+M;int n,m,_fa[N];
bool vis[M];
struct Edge
{int fr,to,val;Edge() {}Edge(int f,int t,int v): fr(f),to(t),val(v) {}bool operator <(const Edge &a)const {return val=n) res=e[i].val-e[p].val;}else if(x!=y)//不要计算重边 {Split(x,y);vis[pos[y]-N]=0, vis[i]=1;//别忘了Splay(y)后再用y的信息pos[y]！而且要先用pos[y]清vis再Cut().while(!vis[p]) ++p;Cut(pos[y]), Link(i);if(k>=n) res=std::min(res,e[i].val-e[p].val);}}printf("%d",res);return 0;
}