算是个笔记好了。

众所周知，Kruskal 重构树干的事情本质上是：把树上路径边权最大值查询转换为 LCA 问题。但同时我们还有另外一种搞法，可以把它转化成 RMQ。

具体来说，在 Kruskal 的过程中，对于每个连通块维护一条链。初始的时候链只有孤点，在合并连通块时，把两端连通块的链首尾相接，中间连边的权值就是当前边权。在最后得到的这个链的结构上，两点间边权的最大值就等于是两点在树上边权的最大值。

为了证明这一点，我们可以先观察到一个事情：链和重构树只是连通块内部的两种结构，对于大的连通性并没有影响。换句话说，对于任何 $w$，仅保留原树中 $\le w$ 的边，那么两种结构维护下的任意连通状态完全没有任何区别。然后链上 RMQ 和树上路径最大值都可以认为是找到最大的 $w$ 使得仅保留原树中 $\le w$ 的边，指定的两点连通。于是我们的这个算法就是正确的。

这个链的结构显然是用链表结构会比较方便。当然启发式合并复杂度也是对的。然后这里不管是 RMQ 还是找连通性刻画（就是一般在 Kruskal 重构树上跳倍增的玩意）实际上 ST 表线段树也好四毛子也好都会好搞的。就算是最朴素的 ST 表，相比于重构树也能省下一半空间。

以下是 [SCOI2013]摩托车交易 的代码，写挺丑的，还要开 C++20，感性理解一下就好。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e5 + 9;
int fa[N];
int findf(int x) { return x == fa[x] ? x : fa[x] = findf(fa[x]); }
int n, m, q, id[N], b[N], rt;
int ed[N], nxt[N], pos[N];
ll val[N], sgt[N << 1];
ll dst(int u, int v) {
  ll ret = LLONG_MAX;
  if ((u = pos[u]) > (v = pos[v])) swap(u, v);
  for (u += n, v += n; u < v; u >>= 1, v >>= 1) {
    if (u & 1) ret = min(ret, sgt[u++]);
    if (v & 1) ret = min(ret, sgt[--v]);
  }
  return ret;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i) cin >> id[i];
  for (int i = 1; i <= n; ++i) cin >> b[i];
  vector<tuple<ll, int, int>> es(m);
  for (auto& [w, u, v] : es) cin >> u >> v >> w;
  for (int i = 1; i <= n; ++i) fa[i] = ed[i] = i;
  for (int x, rt = 0; q; --q, rt = x)
    if (cin >> x; rt) es.emplace_back(LLONG_MAX, rt, x);
  for (ranges::sort(es, greater()); auto [w, u, v] : es)
    if ((u = findf(u)) != (v = findf(v)))
      nxt[ed[u]] = v, val[ed[u]] = w, ed[fa[v] = u] = ed[v];
  for (int i = 1; i <= n; ++i)
    if (fa[i] == i) {
      for (int j = 0; j < n; ++j) sgt[(pos[i] = j) + n] = val[i], i = nxt[i];
      break;
    }
  for (int i = n - 1; i; --i) sgt[i] = min(sgt[i << 1], sgt[i << 1 | 1]);
  ll tmp = 0;
  if (b[id[1]] < 0)
    cout << 0 << '\n';
  else
    tmp = b[id[1]];
  for (int i = 2; i <= n; ++i)
    if (tmp = min(tmp, dst(id[i - 1], id[i])); b[id[i]] > 0)
      tmp += b[id[i]];
    else
      cout << min(-(ll)b[id[i]], tmp) << '\n', tmp = max(tmp + b[id[i]], 0ll);
  return cout << flush, 0;
}

以下是另一份很丑的 [NOIP2013 提高组] 货车运输 的代码，可以看到这个结构在图不保证连通的时候实际上代码变化极少。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e4 + 9;
int fa[N];
int findf(int x) { return x == fa[x] ? x : fa[x] = findf(fa[x]); }
int n, m, q;
int ed[N], nxt[N], pos[N];
int val[N], sgt[N << 1];
int dst(int u, int v) {
  int ret = INT_MAX;
  if ((u = pos[u]) > (v = pos[v])) swap(u, v);
  for (u += n, v += n; u < v; u >>= 1, v >>= 1) {
    if (u & 1) ret = min(ret, sgt[u++]);
    if (v & 1) ret = min(ret, sgt[--v]);
  }
  return ret;
}
signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  vector<tuple<int, int, int>> es(m);
  for (auto& [w, u, v] : es) cin >> u >> v >> w;
  for (int i = 1; i <= n; ++i) fa[i] = ed[i] = i;
  memset(val + 1, -1, n * sizeof(int));
  for (ranges::sort(es, greater()); auto [w, u, v] : es)
    if ((u = findf(u)) != (v = findf(v)))
      nxt[ed[u]] = v, val[ed[u]] = w, ed[fa[v] = u] = ed[v];
  for (int i = 1, j = -1; i <= n; ++i)
    if (fa[i] == i)
      for (int x = i; x; x = nxt[x]) sgt[(pos[x] = ++j) + n] = val[x];
  for (int i = n - 1; i; --i) sgt[i] = min(sgt[i << 1], sgt[i << 1 | 1]);
  for (cin >> q; q; --q) {
    int u, v;
    cin >> u >> v;
    cout << dst(u, v) << '\n';
  }
  return cout << flush, 0;
}