结论

感觉答案是最大生成树上路径 $u\to v$ 的最小的那条边 $(a,b)$ 的权。简要说明一下：

考虑 kruskal 算法建出的生成树。

假设存在一条比生成树上更优的路径 A，不妨假设这条路径上瓶颈边为 (a',b')。

我们会发现，在建树过程中 (a,b) 考虑的时间是在 A 上所有边之后的。

此时 u,v 早已联通，该边是不可能在生成树上的。与假设矛盾。

怎样算答案？

如果把边权最小值换为两点距离你肯定会做: LCA。

如果把树换成序列你肯定更会做： 倍增 （ST表）

那不就可以考虑倍增维护最小值吗？设 $f(u,i)$ 为 $u$ 向上跳 $2^i$ 次边权最小值，一边求 LCA 一边算最小值。

原图不是不联通吗，我们在连边的时候用并查集维护一下连通性。

加边，将不同连通块都连在一起。这些边的边权直接设为 -1。这样就规避了上篇题解的问题。

时间复杂度 $O((n+m)\log(n+m)+q\log n)$

这题要是放到今天，差不多是 D2T1，当年可是 D1T3（假设还是考两天）。

听懂了就点个赞呗 ^v^

代码

我没乱写，大家伙可以看看。

#include<bits/stdc++.h>
#define inf 1000000007
using namespace std;
inline int read(){
    int s=0;
    char ch=getchar();
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){
        s*=10,s+=ch-'0';
        ch=getchar();
    }
    return s;
}
int n,m,vis[10099],dp[10099],f[10099][28],mi[10099][28];
pair<int,pair<int,int> >e[222222];
//不想写结构体和 cmp 可以用 pair,排序中 first 比 second 优先。
vector<int>t[10099],w[10099];
int fa[10099],now;
int find(int x){
    if(fa[x]==x)return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
void reset(){
    for(int i=1;i<=n;++i)fa[i]=i;
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
void dfs(int x,int d){
    if(vis[x])return;
    vis[x]=1;
    dp[x]=d;
    for(int i=0;i<t[x].size();++i){
        if(vis[t[x][i]]==0){
            dfs(t[x][i],d+1);
            f[t[x][i]][0]=x;
        }
    }
}
int lca(int x,int y){
    int ans=inf;
    if(dp[x]<dp[y])swap(x,y);
    while(dp[x]>dp[y]){
        ans=min(ans,mi[x][(int)log2(dp[x]-dp[y])]);
        x=f[x][(int)log2(dp[x]-dp[y])];
    }
    if(x==y)return ans;
    for(int i=22;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            ans=min(ans,min(mi[x][i],mi[y][i]));
            x=f[x][i],y=f[y][i];
        }
    }
    return min(ans,min(mi[x][0],mi[y][0]));
}
int main(){
    memset(mi,0x7f,sizeof(mi));
    n=read(),m=read();
    reset();
    for(int i=1;i<=m;++i){
        int u=read(),v=read(),c=read();
        e[++now]=make_pair(c,make_pair(u,v));
        merge(u,v);
    }
    //加边
    for(int i=1;i<=n;++i){
        if(find(1)!=find(i)){
            merge(1,i);
            e[++now]=make_pair(-1,make_pair(1,i));      
        }
    }
    sort(e+1,e+now+1);
    reset();
    for(int cnt=1,p=now;cnt<n;++cnt){
        int u=e[p].second.first;
        int v=e[p].second.second;
        while(find(u)==find(v)){
            --p;
            u=e[p].second.first;
            v=e[p].second.second;
        }
        merge(u,v);
        t[u].push_back(v);
        t[v].push_back(u);
        w[u].push_back(e[p].first);
        w[v].push_back(e[p].first);
        --p;
    }
    dfs(1,0);
    f[1][0]=1;
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            f[u][i]=f[f[u][i-1]][i-1];
        }
    }
    for(int x=1;x<=n;++x){
        for(int i=0;i<t[x].size();++i){
            int u=t[x][i],v=x;
            if(u>v)continue;
            if(f[u][0]==v)mi[u][0]=w[x][i];
            else mi[x][0]=w[x][i];
        }
    }
    for(int i=1;i<=26;++i){
        for(int u=1;u<=n;++u){
            mi[u][i]=min(mi[f[u][i-1]][i-1],mi[u][i-1]);
        }
    }
    int q=read();
    for(int i=1;i<=q;++i)
        printf("%d\n",lca(read(),read()));
    return 0;
}