LCA+最大生成树

就是求出最大生成树后两点之间路径都唯一，所以两点路径必经过他们的的LCA。（这些相信不要我说吧）

样例没过，提交上去也全WA

#include <bits/stdc++.h>
using namespace std;
int en;
int first[500005];  // first[i]代表当前第i个点的链表的第一条边的编号

int read() {
    char c = ' ';
    int f = 1, x = 0;
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
void wr(int x) {
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        wr(x / 10);
    putchar(x % 10 + '0');
}

struct edge {
    int e, d;  //终点，长度
    int next;  //下一个点的编号
} ed[1000455];

struct stu {
    int x, y, dis;
} iee[1000455];

int n, m;
int f[500005][25], depth[500005];  // f[i][j]代表i向上走2^j次方步会走到哪里，depth[i]代表i号点的深度
int w[500005][25];
int dp[500005];
bool vis[500005];

bool cmp(stu x, stu y) { return x.dis > y.dis; }
void add_edge(int s, int e, int d) {
    ed[++en].e = e;
    ed[en].d = d;
    ed[en].next = first[s];
    first[s] = en;
}

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

void kelu() {
    sort(iee, iee + m + 1, cmp);
    for (int i = 1; i <= n; i++) dp[i] = i;
    for (int i = 1; i <= m; i++) {
        if (find(iee[i].x) != find(iee[i].y)) {
            dp[find(iee[i].x)] = find(iee[i].y);
            add_edge(iee[i].x, iee[i].y, iee[i].dis);
            add_edge(iee[i].y, iee[i].x, iee[i].dis);
        }
    }
}

void dfs(int now, int fa) {
    f[now][0] = fa;
    depth[now] = depth[fa] + 1;
    for (int i = 1; i <= 18; i++) {
        f[now][i] = f[f[now][i - 1]][i - 1];
        w[now][i] = min(w[now][i - 1], w[f[now][i - 1]][i - 1]);
    }

    for (int p = first[now]; p != 0; p = ed[p].next) {
        int e = ed[p].e;  // now----e;
        if (e == fa) continue;
        w[e][0] = ed[p].d;
        dfs(e, now);
    }
}

int LCA(int p1, int p2) {
    if (find(p1) != find(p2))
        return -1;
    int ans = 0x3f3f3f3f;
    if (depth[p1] < depth[p2])
        swap(p1, p2);
    for (int a = 18; a >= 0; a--) {
        if (depth[f[p1][a]] >= depth[p2]) {
            ans = min(ans, w[p1][a]);
            p1 = f[p1][a];
        }
    }
    if (p1 == p2) {
        return ans;
    }
    for (int a = 18; a >= 0; a--) {
        if (f[p1][a] != f[p2][a]) {
            ans = min(ans, min(w[p1][a], w[p2][a]));
            p1 = f[p1][a];
            p2 = f[p2][a];
        }
    }
    ans = min(ans, min(w[p1][0], w[p2][0]));
    return ans;
}

int qqq;  //数据组数
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> iee[i].x >> iee[i].y >> iee[i].dis;
    }
    kelu();
    dfs(1, 0);
    cin >> qqq;
    for (int i = 1; i <= qqq; i++) {
        int p1;
        int p2;
        p1 = read();
        p2 = read();
        wr(LCA(p1, p2));
        printf("\n");
    }
}