思路：

Kruskal求最大生成树+倍增LCA

// by SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 105000int n,m,tot=0,xx,yy,zz,ans;int first[N],v[N*10],next[N*10],w[N*10],f[N],dep[N],fa[N][20],minn[N][20];int find(int x){return x==f[x]?x:f[x]=find(f[x]);}struct EDGE{int from,to,weight;}Edge[50500];void add(int x,int y,int z){    w[tot]=z,v[tot]=y;    next[tot]=first[x];    first[x]=tot++;}bool cmp(EDGE x,EDGE y){return x.weight>y.weight;}void dfs(int x){    for(int j=1;j<=18;j++){
             fa[x][j]=fa[fa[x][j-1]][j-1];        minn[x][j]=min(minn[x][j-1],minn[fa[x][j-1]][j-1]);    }    for(int i=first[x];~i;i=next[i])        if(dep[v[i]]==-1){
                 dep[v[i]]=dep[x]+1;            fa[v[i]][0]=x;minn[v[i]][0]=w[i];            dfs(v[i]);        }}int lca(int x,int y){    int ans=0x3fffffff;    if(dep[x]
        
         =0;i--)if(dep[x]>=dep[y]+(1<
         
          =0;i--)        if(fa[x][i]!=fa[y][i]){
                 ans=min(ans,min(minn[x][i],minn[y][i]));            x=fa[x][i];y=fa[y][i];        }    return min(ans,min(minn[x][0],minn[y][0]));}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)f[i]=i;     memset(dep,-1,sizeof(dep));    memset(minn,0x3f,sizeof(minn));    memset(first,-1,sizeof(first));    for(int i=1;i<=m;i++){
             scanf("%d%d%d",&xx,&yy,&zz);        Edge[i].from=xx;Edge[i].to=yy;Edge[i].weight=zz;    }    sort(Edge+1,Edge+1+m,cmp);    for(int i=1;i<=m;i++)        if(find(Edge[i].from)!=find(Edge[i].to)){
                 f[find(Edge[i].from)]=find(Edge[i].to);            add(Edge[i].from,Edge[i].to,Edge[i].weight);            add(Edge[i].to,Edge[i].from,Edge[i].weight);        }    dep[find(1)]=0;dfs(find(1));    scanf("%d",&m);    while(m--){
             scanf("%d%d",&xx,&yy);        if(~dep[xx]&&~dep[yy])printf("%d\n",lca(xx,yy));        else puts("-1");    }}
         
        
       
      
     

队长讲了还有一中很奇怪的方法可以乱搞。

就是：Bling 并查集！

我们可以想到Kruskal进行的过程中是把两个连通块连起来，中间连的边一定比连通块里面的边要小。

那么我们可以考虑按秩合并。。可以证明这样树的高度是log的。

然后直接暴力求LCA即可

网上是这么说的：

启发式并查集，就是维护每个集合的深度，在合并两个集合的时候把小的那个集合挂在大集合下。

在此题中呢，求最大生成树的同时，不把新加入的一条边作为计算答案的树，而是把两个集合的祖先加入树中，边权就是原来边的两个边权。看到这，不禁产生了疑问，树的边权和形态与求出的最大生成树都不一样，为啥能做？？？其实没有关系，因为新加入的边不影响

原来集合中两点的答案，合并的两个集合中的点合并后肯定要经过原来这条边，那我把祖先接起来用原来边的边权也是一样的。

但是这么做，由于使用了启发式合并，那么最后新的树高度可以证明不会超过logn（其实我也不会证大笑），那么我们不用倍增处理这棵树，直接暴力求lca即可，不仅代码短，而且常数小！！！

// by SiriusRen#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 105000int n,m,tot=0,xx,yy,zz;int first[N],v[N*10],next[N*10],w[N*10],f[N],dep[N],fa[N],size[N],minn[N];int find(int x){
    return x==f[x]?x:f[x]=find(f[x]);}struct EDGE{
    int from,to,weight;}Edge[50500];void add(int x,int y,int z){w[tot]=z,v[tot]=y;next[tot]=first[x];first[x]=tot++;}bool cmp(EDGE x,EDGE y){
    return x.weight>y.weight;}void dfs(int x){    for(int i=first[x];~i;i=next[i])        if(dep[v[i]]==-1){            dep[v[i]]=dep[x]+1;            fa[v[i]]=x;minn[v[i]]=w[i];            dfs(v[i]);        }}void lca(int x,int y){    int ans=0x3fffffff;    if(dep[x]>dep[y])swap(x,y);    while(dep[x]!=dep[y])ans=min(minn[y],ans),y=fa[y];    while(x!=y){        ans=min(ans,min(minn[x],minn[y]));        x=fa[x];y=fa[y];    }    printf("%d\n",ans);    return;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)size[i]=1;    for(int i=1;i<=n;i++)f[i]=i;     memset(dep,-1,sizeof(dep));    memset(first,-1,sizeof(first));    memset(minn,0x3f,sizeof(minn));    for(int i=1;i<=m;i++){        scanf("%d%d%d",&xx,&yy,&zz);        Edge[i].from=xx;Edge[i].to=yy;Edge[i].weight=zz;    }    sort(Edge+1,Edge+1+m,cmp);    for(int i=1;i<=m;i++){        int fx=find(Edge[i].from),fy=find(Edge[i].to);        if(fx!=fy){            if(size[fx]>size[fy])swap(fx,fy);            f[fx]=fy;size[fy]+=fx;            add(fx,fy,Edge[i].weight);add(fy,fx,Edge[i].weight);        }    }    dep[find(1)]=0;dfs(find(1));    scanf("%d",&m);    while(m--){        scanf("%d%d",&xx,&yy);        if(~dep[xx]&&~dep[yy])lca(xx,yy);        else puts("-1");    }}