Kruskal 重构树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000 + 5;
const int MAXM = 50000 + 5;
int n, m, q;
struct Edge
{
    int u, v, w;
};
bool cmp(Edge a, Edge b)
{
    return a.w > b.w;
}
Edge e[MAXM];     //原图
int fa[MAXN * 2]; //并查集
int findFa(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = findFa(fa[x]);
}
int tot, rt;             //点数，新根
vector<int> g[MAXN * 2]; //重构树的连接关系
int w[MAXN * 2];         //重构树的点权
//lca
int dep[MAXN * 2];
int lg[MAXN * 2];
int f[MAXN * 2][32];
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i <= lg[dep[u]]; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
int lca(int x, int y)
{
    if (dep[x] < dep[y])
        swap(x, y);
    while (dep[x] > dep[y])
        x = f[x][lg[dep[x] - dep[y]] - 1];
    if (x == y)
        return x;
    for (int k = lg[dep[x]] - 1; k >= 0; --k)
        if (f[x][k] != f[y][k])
            x = f[x][k], y = f[y][k];
    return f[x][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //输入
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    //kruskal 重构树
    for (int i = 1; i <= n * 2; i++)
        fa[i] = i;
    sort(e + 1, e + m + 1, cmp);
    tot = n;
    for (int i = 1; i <= m; i++)
    {
        int faU = findFa(e[i].u);
        int faV = findFa(e[i].v);
        int nowW = e[i].w;
        if (faU == faV)
            continue;
        tot++;
        fa[faU] = fa[faV] = tot;
        g[tot].push_back(faU);
        g[tot].push_back(faV);
        w[tot] = nowW;
    }
    rt = tot + 1;
    w[rt] = -1;
    for (int i = 1; i <= tot; i++)
        if (findFa(i) == i)
            g[rt].push_back(i);
    tot++;
    //lca预处理
    for (int i = 1; i <= tot; ++i)
        lg[i] = lg[i - 1] + ((1 << lg[i - 1]) == i);
    dep[0] = 0;
    dfs(rt, 0);
    //输出
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;
        cout << w[lca(u, v)] << "\n";
    }
    return 0;
}