Aimee

"Doctor，你这水平下降的有点。。。"

'"我怎么知道能手残写了个return p"

很显然，那条路径一定在最大生成树上，然后在这条树上跑LCA即可

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct e{
    int to;
    int ne;
    int v;
    int st;
    int f;
}ed[500010],e2[500010];
int n,m;
int x,y,z;
int fa[500010];
int head[500010];
int vis[500001];
int p;
int dep[500010];
int logg[500010];
int ff[500010][50];
int p1;
int md[500010][50];
void add(int f,int to,int v){
    p++;
    ed[p].to=to;
    ed[p].v=v;
    ed[p].f=f;
    return ;
}
void add1(int f,int to,int v){
    p1++;
    e2[p1].ne=head[f];
    e2[p1].to=to;
    e2[p1].v=v;
    head[f]=p1;
    return ;
}
bool cmp(e x,e y){
    return x.v>y.v;
}
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void kr(){
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    sort(ed+1,ed+m+1,cmp);
    int num=0;
    for(int i=1;i<=m;i++){
        int u=find(ed[i].to);
        int v=find(ed[i].f);
        if(u!=v){
            add1(ed[i].f,ed[i].to,ed[i].v);
            add1(ed[i].to,ed[i].f,ed[i].v);
            fa[u]=v;
            if(++num==n)
            return ;
        }
    }
}
void dfs(int now,int fr,int vv){
//  cout<<now<<" s"<<dep[fr]+1<<endl;
    dep[now]=dep[fr]+1;
    vis[x]=1;
    ff[now][0]=fr;
    md[now][0]=vv;
    for(int i=1;(1<<i)<=dep[now];++i){
        ff[now][i]=ff[ff[now][i-1]][i-1];
        md[now][i]=min(md[now][i-1],md[ff[now][i-1]][i-1]);
    }
    for(int i=head[now];i;i=e2[i].ne){
        if(e2[i].to!=fr){
            dfs(e2[i].to,now,e2[i].v);
        }
    }
}
int q;
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    int znx=210000000;
//  cout<<dep[x];
    while(dep[x]>dep[y]){    
    //cout<<dep[x]-dep[y]; 
        znx=min(znx,md[x][logg[dep[x]-dep[y]]-1]);
        x=ff[x][logg[dep[x]-dep[y]]-1];

//  cout<<"log"<<logg[dep[x]-dep[y]];
//  cout<<endl<<dep[x]-dep[y];
    }
    if(x==y)
    return znx;
//  cout<<343243432;
    for(int k=logg[dep[x]]-1;k>=0;k--){
        if(ff[x][k]!=ff[y][k]){
            znx=min(znx,md[x][k]);
            znx=min(znx,md[y][k]);
            x=ff[x][k];
            y=ff[y][k];

        }
    }
    return znx=min(znx,min(md[x][0],md[y][0]));
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    kr();
    for(int i=1;i<=n;++i){
        logg[i]=logg[i-1]+(1<<logg[i-1]==i);
    }

    for(int i=1;i<=n;++i){
    //  cout<<i<<endl;
        if(!vis[i]){
            dfs(i,0,0);
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d",&x,&y);
        if(find(x)!=find(y)){
            cout<<-1<<endl; 
        } else{
            cout<<lca(x,y)<<endl;
        }
    }
    return 0;
}