kruskal重构树 马蜂优良TLE 0

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
using namespace std;

const int N = 5e4+10;
int n, m, tot, h[N], dsu[N], val[N]; 
int dep[N], siz[N], son[N], top[N], fa[N];
int idx; struct Forward_star{int to, ne;} e[N];
struct Edges{int u, v, w;} g[N];
bool cmp(Edges x, Edges y) {return x.w > y.w;}
void add_edge(int u, int v) {
    e[++ idx].to = v;
    e[idx].ne = h[u];
    h[u] = idx;
}

int find(int x) {
    if(x != dsu[x]) dsu[x] = find(dsu[x]);
    return dsu[x];
}

int dfs1(int u) {
    siz[u] = 1;
    son[u] = -1;
    for(int i = h[u]; ~i; i = e[i].ne) {
        int v = e[i].to;
        if(dep[v]) continue;
        fa[v] = u;
        dep[v] = dep[u] + 1;
        dfs1(v);
        siz[u] += siz[v];
        if(!~son[u] || siz[son[u]] < siz[v])
            son[u] = v;
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    if(~son[u]) dfs2(son[u], t);
    for(int i = h[u]; ~i; i = e[i].ne) 
        if(e[i].to != son[u] && e[i].to != fa[u])
            dfs2(e[i].to, e[i].to);
}

int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] > dep[v] ? v : u;
}

inline void kruskal() {
    sort(g + 1, g + m + 1, cmp);
    for(int i = 1; i <= m; i ++) {
        int u = find(g[i].u), v = find(g[i].v);
        if(u != v) {
            val[++ tot] = g[i].w;
            dsu[u] = dsu[v] = dsu[tot] = tot;
            add_edge(u, tot);
            add_edge(tot, u);
            add_edge(v, tot);
            add_edge(tot, v);
        }
    }
    for(int i = 1; i <= n; i ++) {
        if(dep[i]) continue;
        int f = find(i);
        dep[f] = 1;
        dfs1(f); 
        dfs2(f, f);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    memset(h, -1, sizeof h);
    cin >> n >> m; tot = n;
    for(int i = 1; i <= n; i ++) dsu[i] = i;
    for(int i = 1; i <= m; i ++)
        cin >> g[i].u >> g[i].v >> g[i].w;
    kruskal();
    int q, u, v;
    cin >> q;
    // for(int i = 1; i <= tot; i ++)
    //     cout << dep[i] << ' ';
    while(q --) {
        cin >> u >> v;
        if(find(u) != find(v)) cout << "-1\n";
        else cout << val[lca(u, v)] << '\n';
    }
}