【题意】给定N<=5*10^4,M<=1*10^5的图，Q<=5*10^4个询问，（u，v）选择一条路径使得最大的边权最小。

【解题方法】找最小，显然先MST。然后用倍增搞一搞就行了，熟练剖分也可以，算是树剖入门题了，我这里用倍增来搞一下。

【AC 代码】

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5e5+10;
const int maxm = 1e6+10;
int n,m,q;
struct edge1{
    int u,v,w;
    bool operator<(const edge1 &rhs) const{
        return w<rhs.w;
    }
};
vector<edge1>E1;
int head[maxn],tot;
struct edge{
    int v,w,next;
}E[maxm];
void init()
{
    memset(head,-1,sizeof(head));
    tot=0;
}
void addedge(int u,int v,int w)
{
    E[tot].v=v,E[tot].w=w,E[tot].next=head[u],head[u]=tot++;
}
int fa[maxn];
int Find(int x)
{
    if(x==fa[x]) return x;
    else return fa[x]=Find(fa[x]);
}
void Kruskal()
{
    for(int i=1; i<=n; i++) fa[i]=i;
    sort(E1.begin(),E1.end());
    init();
    int num=0;
    for(auto &e:E1)
    {
        int u=Find(e.u),v=Find(e.v);
        if(u==v) continue;
        fa[u]=v;
        addedge(e.u,e.v,e.w);
        addedge(e.v,e.u,e.w);
        ++num;
        if(num==n-1) break;
    }
}
int dep[maxn],p[20][maxn],maxv[20][maxn];
void dfs(int u,int f,int d,int w)
{
    dep[u]=d;
    p[0][u]=f,maxv[0][u]=w;
    for(int i=head[u]; ~i; i=E[i].next)
    {
        int v=E[i].v;
        if(v==f) continue;
        dfs(v,u,d+1,E[i].w);
    }
}
void build()
{
    dfs(1,-1,0,0);
    for(int i=0; i+1<18; i++)
    {
        for(int v=1; v<=n; v++)
        {
            if(p[i][v]<0) p[i+1][v]=-1;
            else p[i+1][v]=p[i][p[i][v]];
            maxv[i+1][v] = max(maxv[i][v],maxv[i][p[i][v]]);
        }
    }
}
int lca(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    for(int i=0; i<18; i++) if(dep[u]-dep[v]>>i&1) v=p[i][v];
    if(u==v) return u;
    for(int i=17; ~i; i--)
        if(p[i][u]!=p[i][v])
            u=p[i][u],v=p[i][v];
    return p[0][u];
}
int get(int u,int to)
{
    int ret=0;
    for(int i=0; i<18; i++)
        if(dep[u]-dep[to]>>i&1) ret=max(ret,maxv[i][u]),u=p[i][u];
    return ret;
}
int main()
{
    int cas=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        E1.clear();
        int u,v,w;
        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            E1.push_back(edge1{u,v,w});
        }
        Kruskal();
        build();
        scanf("%d",&q);
        if(cas++) printf("\n");
        while(q--)
        {
            scanf("%d%d",&u,&v);
            int _lca=lca(u,v);
            printf("%d\n",max(get(u,_lca),get(v,_lca)));
        }
    }
    return 0;
}