给定一张图， \(q\) 组询问从 \(s_i\) 到 \(t_i\) 路径上最大边权的最小值。
\(n < 10^4\)，\(m < 5 \times 10^4\)，\(q<3\times10^4\)。
首先，所有询问的答案均在原图的最小生成树上，是最小生成树的瓶颈边，因为任何不在最小生成树上的边一定比原边更大，然后问题就变成寻找树上2点的路径上边权最大值，直接用倍增处理LCA时多处理 \(g[i][j]\) 来记录点 \(i\) 的 \(2^j\) 祖先中所有路径的最大值，然后在跳LCA时得出答案。
#include<bits/stdc++.h>
using namespace std;
int n,q,m;
struct edge{
int to,w,from;
bool operator <(const edge A)const{
return w>A.w;
}
}e[50005];
struct edge1{
int to,nxt,w;
}e1[20005];
int head[10005],ecnt1,fa[10005],f[10005][18],g[10005][18],dep[10005],bj[10005];
int findfa(int x){
return (fa[x]==x)?x:fa[x]=findfa(fa[x]);
}
inline void adde1(int u,int v,int w){
e1[++ecnt1].nxt=head[u];
e1[ecnt1].to=v;
e1[ecnt1].w=w;
head[u]=ecnt1;
}
void dfs(int u,int fa){
bj[u]=1;
for(int i=1;i<=17&&fa!=0;++i){
f[u][i]=f[f[u][i-1]][i-1];
g[u][i]=min(g[u][i-1],g[f[u][i-1]][i-1]);
}
for(int i=head[u];i;i=e1[i].nxt){
int v=e1[i].to;
if(v==fa)
continue;
f[v][0]=u;
g[v][0]=e1[i].w;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
int lca(int x,int y){
int ret=1e9;
if(dep[x]<dep[y])
swap(x,y);
for(int i=17;i>=0;--i){
if(dep[f[x][i]]>=dep[y]){
ret=min(ret,g[x][i]);
x=f[x][i];
}
}
if(x==y)
return ret;
for(int i=17;i>=0;--i){
if(f[x][i]!=f[y][i]){
ret=min(ret,g[x][i]);
ret=min(ret,g[y][i]);
x=f[x][i];
y=f[y][i];
}
}
ret=min(ret,g[x][0]);
ret=min(ret,g[y][0]);
return ret;
}
int main(){
memset(g,0x3f,sizeof g);
scanf("%d %d",&n,&m);
for(int i=1;i<=m;++i){
int x,y,w;
scanf("%d %d %d",&x,&y,&w);
e[i].from=x;
e[i].to=y;
e[i].w=w;
}
for(int i=1;i<=n;++i){
fa[i]=i;
}
sort(e+1,e+m+1);
for(int i=1;i<=m;++i){
if(findfa(e[i].from)!=findfa(e[i].to)){
fa[findfa(e[i].from)]=findfa(e[i].to);
adde1(e[i].from,e[i].to,e[i].w);
adde1(e[i].to,e[i].from,e[i].w);
}
}
for(int i=1;i<=n;++i){
if(bj[i]==0){
dfs(i,0);
}
}
scanf("%d",&q);
while(q--){
int x,y;
scanf("%d %d",&x,&y);
if(findfa(x)!=findfa(y))
puts("-1");
else{
printf("%d\n",lca(x,y));
}
}
return 0;
}