夏令营和济南培训的时候都讲过现在才开始刷
我真的太颓了...
传送门

先放个玄学东西:

思路:

先跑一下kruskal然后，LCA找最小值最大的那条路

代码: 

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>

#define N 50005
#define M 100005
#define INF 999999999

using namespace std;
struct Edge1 {
    int x, y, dis;
}edge1[N];
struct Edge2 {
    int to, next, dis;
}edge2[M];
int head[N], fa[N][21], w[N][21], fath[N], cnt, deep[N], n, m;
bool vis[N];

int read() {
    int s = 0, f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return f ? -s : s;
}

bool CMP(Edge1 x, Edge1 y) {
    return x.dis > y.dis;
}

void add_edge(int from, int to, int dis) {
    edge2[++cnt].next = head[from];
    edge2[cnt].to = to;
    edge2[cnt].dis = dis;
    head[from] = cnt;
}

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

void kruskal() {
    sort(edge1 + 1, edge1 + m + 1, CMP);
    for (int i = 1; i <= n; i++) fath[i] = i; 
    for (int i = 1; i <= m; i++)
        if (find(edge1[i].x) != find(edge1[i].y)) {
            fath[find(edge1[i].x)] = find(edge1[i].y);
            add_edge(edge1[i].x, edge1[i].y, edge1[i].dis);
            add_edge(edge1[i].y, edge1[i].x, edge1[i].dis);
        }
}

void dfs(int node) {
    vis[node] = true;
    for (int i = head[node]; i; i = edge2[i].next) {
        int to = edge2[i].to;
        if (vis[to]) continue;
        deep[to] = deep[node] + 1;
        fa[to][0] = node;
        w[to][0] = edge2[i].dis;
        dfs(to);
    }
}

int lca(int x, int y) {
    if (find(x) != find(y)) return -1;
    int ans = INF;
    if (deep[x] > deep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (deep[fa[y][i]] >= deep[x]) {
            ans = min(ans, w[y][i]);
            y = fa[y][i];   
        }
    if (x == y) return ans;
    for (int i = 20; i >= 0; i--) 
        if (fa[x][i] != fa[y][i]) {
            ans = min(ans, min(w[x][i], w[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    ans = min(ans, min(w[x][0], w[y][0]));
    return ans;
}

int main() {
    n = read(), m = read();
    for (int i = 1, x, y, dis; i <= m; i++) {
        x = read(), y = read(), dis = read();
        edge1[i].x = x, edge1[i].y = y, edge1[i].dis = dis;
    }
    kruskal();
    for (int i = 1; i <= n; i++) 
        if (!vis[i]) {
            deep[i] = 1;
            dfs(i);
            fa[i][0] = i;
            w[i][0] = INF;
        }
    for (int i = 1; i <= 20; i++)
        for (int j = 1; j <= n; j++) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
            w[j][i] = min(w[j][i - 1], w[fa[j][i - 1]][i - 1]);
        }
    int s = read();
    for (int i = 1, x, y; i <= s; i++) {
        x = read(), y = read();
        printf("%d\n", lca(x, y));
    }
    return 0;
}