LCT 7pts MLE 悬关求调

#include <bits/stdc++.h>
//#define int long long
#define PII pair<int, int>

using namespace std;

int n, m, q;
struct EDGE
{
	int u, v, w;
	bool operator < (const EDGE xx) const
	{
		return w < xx.w;
	}
}edge[200010];
bool vis[200010];
int idx;
struct node
{
	int fa;
	int ls, rs;
	int mx;
	bool lz;
}tree[400010];
int ans = 1145141919810;

bool isroot(int u)
{
	return tree[tree[u].fa].ls != u && tree[tree[u].fa].rs != u;
}

void pushup(int x)
{
	tree[x].mx = x;
	if(tree[tree[x].ls].mx > n && (tree[x].mx <= n || tree[x].mx > tree[tree[x].ls].mx)) tree[x].mx = tree[tree[x].ls].mx;
	if(tree[tree[x].rs].mx > n && (tree[x].mx <= n || tree[x].mx > tree[tree[x].rs].mx)) tree[x].mx = tree[tree[x].rs].mx;
}

void pushdown(int u)
{
    if(tree[u].lz)
	{
        swap(tree[u].ls, tree[u].rs);
        if(tree[u].ls) tree[tree[u].ls].lz ^= 1;
        if(tree[u].rs) tree[tree[u].rs].lz ^= 1;
        tree[u].lz = false;
    }
}

void push(int u)
{
    if(!isroot(u)) push(tree[u].fa);
    pushdown(u);
}

void rotate(int u)
{
    int fa = tree[u].fa, gfa = tree[fa].fa;
    if(!isroot(fa))
	{
        if(tree[gfa].ls == fa) tree[gfa].ls = u;
        else tree[gfa].rs = u;
    }
    tree[u].fa = gfa;
    if(tree[fa].ls == u)
	{
        tree[fa].ls = tree[u].rs;
        if(tree[u].rs) tree[tree[u].rs].fa = fa;
        tree[u].rs = fa;
    }
	else
	{
        tree[fa].rs = tree[u].ls;
        if(tree[u].ls) tree[tree[u].ls].fa = fa;
        tree[u].ls = fa;
    }
    tree[fa].fa = u;
    pushup(fa);
    pushup(u);
}

void splay(int u)
{
    push(u);
    while(!isroot(u))
	{
        int fa = tree[u].fa;
        int gfa = tree[fa].fa;
        if(!isroot(fa))
		{
            if((tree[gfa].ls == fa) == (tree[fa].ls == u)) rotate(fa);
            else rotate(u);
        }
        rotate(u);
    }
}

void access(int u)
{
	for(int i = 0; u; i = u, u = tree[u].fa)
	{
		splay(u);
		tree[u].rs = i;
		pushup(u);
	}
}

void makeroot(int u)
{
	access(u);
	splay(u);
	tree[u].lz ^= 1;
}

void split(int u, int v)
{
	makeroot(u);
	access(v);
	splay(v);
}

int findroot(int u)
{
	access(u);
	splay(u);
	while(tree[u].ls)
	{
		pushdown(u);
		u = tree[u].ls;
	}
	splay(u);
	return u;
}

void link(int u, int v)
{
	makeroot(u);
	if(findroot(v) != u) tree[u].fa = v;
}

void cut(int u, int v)
{
    split(u, v);
    tree[v].ls = tree[u].fa = 0;
    pushup(v);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	int idx = 0;
	for(int i = 1;i <= m;i ++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		if(u != v) edge[++ idx] = {u, v, w};
	}
	m = idx;
	sort(edge + 1, edge + m + 1);
//	for(int i = 1;i <= m;i ++) cout << edge[i].u << " " << edge[i].v << " " << edge[i].w << "\n";
	int mr = 1, ltk = n, sum = 0, kkk = 1;
	for(int i = 1;i <= m;i ++)
	{
		ltk ++;
		if(edge[i].u == edge[i].v)
		{
			vis[i] = 1;
			continue;
		}
		if(findroot(edge[i].u) != findroot(edge[i].v)) link(edge[i].u, ltk), link(ltk, edge[i].v), sum ++;
		else
		{
			split(edge[i].u, edge[i].v);
			mr = tree[edge[i].v].mx;
			vis[mr - n] = 1;
			splay(mr);
			tree[tree[mr].ls].fa = tree[tree[mr].rs].fa = 0;
			link(edge[i].u, ltk), link(ltk, edge[i].v);
		}
		while(vis[kkk] && kkk <= i) kkk ++; 
		if(sum >= n - 1 ) ans = min(ans, edge[i].w - edge[kkk].w);
	}
	cout << ans;
	return 0;
}