最大生成树+lca

凡是这种求多对点的距离关系，且无法O(n^2)的题目，都应该想到lac(翻译：瞎猜的)
可以从y总在提高课里，对最小/最大生成树从集合的角度去分析，假设当前有x,y两个点集，x，y的点想互相到达，一定是通过连接xy两点集边权最大的一条边。
lca需要多维护一个从当前点到其2^i个祖先边权的最小值。

时间复杂度

$$O(qlogn)$$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=10010;
int n,m,father[N];
struct eg{
    int u,v,w;
    bool operator < (const eg & b) const {
        return w>b.w;
    }
}edge[50010];
int h[N],e[N*2],nex[N*2],w[N*2],idx;
void add(int x,int y,int z){
    e[idx]=y,w[idx]=z,nex[idx]=h[x],h[x]=idx++;
}
int dep[N],d[N][20],q[N],fa[N][20];
int Find(int x){
    return x==father[x]? x: father[x]=Find(father[x]);
}
void bfs(){
    int hh=0,tt=0;
    q[tt++]=1;
    memset(dep,0x3f,sizeof dep);
    dep[0]=0,dep[1]=1;
    while(hh!=tt){
        int u=q[hh++];
        for(int i=h[u];~i;i=nex[i]){
            int v=e[i],t=w[i];
            if(dep[v]>dep[u]+1){
                dep[v]=dep[u]+1;
                q[tt++]=v;
                fa[v][0]=u;
                d[v][0]=t;
                for(int j=1;j<18;++j){
                    int anc=fa[v][j-1];
                    fa[v][j]=fa[anc][j-1];
                    d[v][j]=min(d[v][j-1],d[anc][j-1]);
                }
            }
        }
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]) swap(x,y);
    int dis=1e9;
    for(int i=17;i>=0;--i){
        if(dep[fa[x][i]]>=dep[y]){
            dis=min(dis,d[x][i]);
            x=fa[x][i];
        }
    }
    if(x!=y){
        for(int i=17;i>=0;--i){
            if(fa[x][i]!=fa[y][i]){
                dis=min(dis,d[x][i]);
                dis=min(dis,d[y][i]);
                x=fa[x][i],y=fa[y][i];
            }
        }
        dis=min(dis,d[x][0]);
        dis=min(dis,d[y][0]);
    }
    return dis;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) father[i]=i;
    for(int i=1;i<=m;++i){
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    memset(h,-1,sizeof h);
    sort(edge+1,edge+1+m);
    for(int i=1;i<=m;++i){
        int u=edge[i].u,v=edge[i].v;
        if(Find(u)!=Find(v)){
            father[Find(u)]=Find(v);
            add(u,v,edge[i].w);
            add(v,u,edge[i].w);
        }
    }
    int q;
    bfs();
    cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        if(Find(x)!=Find(y)) puts("-1");
        else {
            cout<<lca(x,y)<<endl;
        }
    }
    return 0;
}