[做的是这道题](https://www.luogu.com.cn/problem/P4234)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
const int INF = 1e9;
int n, m;
struct LCT{
int ch[N][2], fa[N], rev[N], id[N], val[N];
#define ls ch[u][0]
#define rs ch[u][1]
void clear(int u) { val[u] = id[u] = ls = rs = fa[u] = rev[u] = 0; }
void maintain(int u) {
clear(0);
id[u] = u;
if (ls) if (val[id[ls]] < val[id[u]]) id[u] = id[ls];
if (rs) if (val[id[rs]] < val[id[u]]) id[u] = id[rs];
}
bool get(int u) { return ch[fa[u]][1] == u; }
bool isroot(int u) { clear(0); return u != ch[fa[u]][0] && u != ch[fa[u]][1]; }
void pushdown(int u) {
clear(0);
if (rev[u]) {
if (ls) rev[ls] ^= 1, swap(ch[ls][0], ch[ls][1]);
if (rs) rev[rs] ^= 1, swap(ch[rs][0], ch[rs][1]);
rev[u] = 0;
}
}
void update(int u) {
if (!isroot(u)) update(fa[u]);
pushdown(u);
}
void rotate(int u) {
int f = fa[u], gf = fa[f], chk = get(u);
fa[u] = gf;
if (!isroot(f)) ch[gf][f == ch[gf][1]] = u;
if (ch[u][chk ^ 1]) fa[ch[u][chk ^ 1]] = f;
ch[f][chk] = ch[u][chk ^ 1];
fa[f] = u;
ch[u][chk ^ 1] = f;
maintain(f); maintain(u); maintain(gf);
}
void splay(int u) {
update(u);
for (int f = fa[u]; f = fa[u], !isroot(u); rotate(u))
if (!isroot(f)) rotate(get(f) == get(u) ? f : u);
}
void access(int u) {
for (int f = 0; u; f = u, u = fa[u])
splay(u), ch[u][1] = f, maintain(u);
}
void makeroot(int u) {
access(u); splay(u);
rev[u] ^= 1;
swap(ls, rs);
}
int find(int u) {
access(u); splay(u);
while (ls) u = ls;
splay(u);
return u;
}
void link(int u, int v) {
if (find(u) == find(v)) return;
makeroot(u); splay(u);
fa[u] = v;
}
void cut(int u, int v) {
makeroot(u); access(v); splay(v);
if (ch[v][0] == u && !rs) fa[u] = ch[v][0] = 0;
}
int query(int u, int v) {
makeroot(u); access(v); splay(v);
return id[v];
}
}T;
int ans = 1e9, num, bin[N], l;
struct Edge{
int u, v, w;
bool operator < (const Edge &x) const {
return w < x.w;
}
}a[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
for (int i = 1; i <= n; i++) T.val[i] = INF, T.maintain(i);
sort(a + 1, a + 1 + m);
for (int i = n + 1; i <= n + m; i++) T.val[i] = a[i - n].w, T.maintain(i);
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v;
if (u == v) continue;
if (T.find(u) != T.find(v)) {
T.link(i + n, u), T.link(i + n, v);
bin[i] = 1; num++;
}
else {
int mn = T.query(u, v);
bin[mn - n] = 0;
T.cut(a[mn - n].u, mn); T.cut(mn, a[mn - n].v);
T.link(u, i + n); T.link(i + n, v);
bin[i] = 1;
}
while (!bin[l] && l <= i) l++;
if (num == n - 1) ans = min(ans, a[i].w - a[l].w);
}
printf("%d", ans);
return 0;
}
```
AC代码， 就调换一下isroot就全错
by Qerrj @ 2024-05-09 10:17:35
@[Qerrj](/user/360780) 哪个 `isroot`？放一下 WA 的代码。
by __ycx2010__ @ 2024-05-09 10:25:06
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 6e5 + 10;
const int INF = 1e9;
int n, m;
struct LCT{
int ch[N][2], fa[N], rev[N], id[N], val[N];
#define ls ch[u][0]
#define rs ch[u][1]
void clear(int u) { val[u] = id[u] = ls = rs = fa[u] = rev[u] = 0; }
void maintain(int u) {
clear(0);
id[u] = u;
if (ls) if (val[id[ls]] < val[id[u]]) id[u] = id[ls];
if (rs) if (val[id[rs]] < val[id[u]]) id[u] = id[rs];
}
bool get(int u) { return ch[fa[u]][1] == u; }
bool isroot(int u) { clear(0); return u != ch[fa[u]][0] && u != ch[fa[u]][1]; }
void pushdown(int u) {
clear(0);
if (rev[u]) {
if (ls) rev[ls] ^= 1, swap(ch[ls][0], ch[ls][1]);
if (rs) rev[rs] ^= 1, swap(ch[rs][0], ch[rs][1]);
rev[u] = 0;
}
}
void update(int u) {
if (!isroot(u)) update(fa[u]);
pushdown(u);
}
void rotate(int u) {
int f = fa[u], gf = fa[f], chk = get(u);
fa[u] = gf;
if (!isroot(f)) ch[gf][f == ch[gf][1]] = u;
if (ch[u][chk ^ 1]) fa[ch[u][chk ^ 1]] = f;
ch[f][chk] = ch[u][chk ^ 1];
fa[f] = u;
ch[u][chk ^ 1] = f;
maintain(f); maintain(u); maintain(gf);
}
void splay(int u) {
update(u);
for (int f = fa[u]; !isroot(u), f = fa[u]; rotate(u))
if (!isroot(f)) rotate(get(f) == get(u) ? f : u);
}
void access(int u) {
for (int f = 0; u; f = u, u = fa[u])
splay(u), ch[u][1] = f, maintain(u);
}
void makeroot(int u) {
access(u); splay(u);
rev[u] ^= 1;
swap(ls, rs);
}
int find(int u) {
access(u); splay(u);
while (ls) u = ls;
splay(u);
return u;
}
void link(int u, int v) {
if (find(u) == find(v)) return;
makeroot(u); splay(u);
fa[u] = v;
}
void cut(int u, int v) {
makeroot(u); access(v); splay(v);
if (ch[v][0] == u && !rs) fa[u] = ch[v][0] = 0;
}
int query(int u, int v) {
makeroot(u); access(v); splay(v);
return id[v];
}
}T;
int ans = 1e9, num, bin[N], l;
struct Edge{
int u, v, w;
bool operator < (const Edge &x) const {
return w < x.w;
}
}a[N];
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &a[i].u, &a[i].v, &a[i].w);
for (int i = 1; i <= n; i++) T.val[i] = INF, T.maintain(i);
sort(a + 1, a + 1 + m);
for (int i = n + 1; i <= n + m; i++) T.val[i] = a[i - n].w, T.maintain(i);
for (int i = 1; i <= m; i++) {
int u = a[i].u, v = a[i].v;
if (u == v) continue;
if (T.find(u) != T.find(v)) {
T.link(i + n, u), T.link(i + n, v);
bin[i] = 1; num++;
}
else {
int mn = T.query(u, v);
bin[mn - n] = 0;
T.cut(a[mn - n].u, mn); T.cut(mn, a[mn - n].v);
T.link(u, i + n); T.link(i + n, v);
bin[i] = 1;
}
while (!bin[l] && l <= i) l++;
if (num == n - 1) ans = min(ans, a[i].w - a[l].w);
}
printf("%d", ans);
return 0;
}
```
@[__ycx2010__](/user/819929) 就是splay里面的那个
by Qerrj @ 2024-05-09 10:29:52
```cpp
for (int f = fa[u]; !isroot(u), f = fa[u]; rotate(u))
```
@[__ycx2010__](/user/819929) 这里， 放 ``f = fa[u]``前面就全错
by Qerrj @ 2024-05-09 10:30:59
语法问题。
`f = fa[u], !isroot(u)` 等价于执行 `f=fa[u]`，判断 `!isroot(u)`。
`!isroot(u),f=fa[u]` 等价于执行 `f=fa[u]`，判断 `f=fa[u]`。
by __ycx2010__ @ 2024-05-09 10:33:55
@[Qerrj](/user/360780) 逗号隔开的语句返回值取最后一个。
by __ycx2010__ @ 2024-05-09 10:34:41
@[__ycx2010__](/user/819929) 原来如此， 懂了， 谢谢谢谢
by Qerrj @ 2024-05-09 10:53:42
@[Qerrj](/user/360780) 嘿嘿嘿天天压行，这下被代码辱了吧
by int08 @ 2024-05-10 07:56:10
@[int08](/user/508032) 八嘎
by Qerrj @ 2024-05-10 11:37:00