绕大圈子的代码：线段树+树链剖分+最小生成树。

评测记录

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
inline ll read(){//快读
	ll k=0,flag=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return k*flag;
}
inline void print(ll x){//快写
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
		y=(y<<1)+(y<<3);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
    return ;
}
const int N=3e5+10;
int n,m,num,q,cnt,fth[N],dep[N],fa[N],dfn[N],rnk[N],siz[N],top[N],son[N],a[N];
struct edge{//最小生成树
	int x,y,w;
}mp[N];
struct node{//线段树
	int l,r,ma;
}tree[N<<2];
vector<pii>g[N];
inline bool cmp(edge a,edge b){return a.w<b.w;}//最小生成树重定义 sort 方式
inline int find(int x){//并查集
	if(x==fth[x])return x;
	return fth[x]=find(fth[x]);
}
void dfs(int x,int f){
	fa[x]=f;//标记父亲
	dep[x]=dep[f]+1;//深度等于父亲深度 +1
	siz[x]=1;//记录当前子树大小
	for(auto i:g[x]){
		if(i.se==f)continue;
		a[i.se]=i.fi;//边权转深度较大的点权
		dfs(i.se,x);
		siz[x]+=siz[i.se];//再次记录子树大小
		if(siz[son[x]]<siz[i.se])son[x]=i.se;//标记重儿子
	}
	return ;
}
void dfs2(int x,int tp){
	top[x]=tp;//记录当前点所在链的头
	dfn[x]=++cnt;
	rnk[cnt]=x;
	if(son[x])dfs2(son[x],tp);//先递归重儿子
	for(auto i:g[x]){
		if(i.se==fa[x]||i.se==son[x])continue;
		dfs2(i.se,i.se);
	}
	return ;
}
void build(int i,int l,int r){//建树
	tree[i].l=l;
	tree[i].r=r;
	if(l==r){
		tree[i].ma=a[rnk[l]];
		return ;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	tree[i].ma=max(tree[i<<1].ma,tree[i<<1|1].ma);
	return ;
}
int query(int i,int l,int r){//线段树区间查找最值
	if(l<=tree[i].l&&tree[i].r<=r)return tree[i].ma;
	int mid=tree[i].l+tree[i].r>>1,res=-1e9;
	if(l<=mid)res=max(res,query(i<<1,l,r));
	if(mid+1<=r)res=max(res,query(i<<1|1,l,r));
	return res;
}
inline int lca(int x,int y){//最近公共祖先查最小可能值
	int res=-1e9;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			res=max(res,query(1,dfn[top[x]],dfn[x]));
			x=fa[top[x]];//x 向上跳
		}
		else{
			res=max(res,query(1,dfn[top[y]],dfn[y]));
			y=fa[top[y]];//y 向上跳
		}
	}
	if(dep[x]<dep[y])res=max(res,query(1,dfn[x],dfn[y]));
   //处于同一链后再查找一边区间最值
	else res=max(res,query(1,dfn[y],dfn[x]));
	return res;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int u=read(),v=read(),w=read();
		mp[++cnt]={u,v,w};//建立最小生成树
	}
	for(int i=1;i<=n;++i)fth[i]=i;//并查集初始化
	sort(mp+1,mp+1+cnt,cmp);//最小生成树排序
	for(int i=1;i<=cnt;++i){
		int x=find(mp[i].x);
		int y=find(mp[i].y);
		if(x==y)continue;//已经链接就跳出
		++num;
		fth[x]=y;
		int u=mp[i].x;
		int v=mp[i].y;
		int w=mp[i].w;
		g[u].pb({w,v});//链接，建图
		g[v].pb({w,u});
		if(num==n-1)break;//建完图退出
	}
	cnt=0;
	dfs(1,0);//树链剖分两遍 dfs
	dfs2(1,1);
	build(1,1,n);//建线段树
	cin>>q;
	while(q--){
		int x=read(),y=read();
		if(find(x)!=find(y))puts("impossible");//没链接就说明是独立点
		else{
			print(lca(x,y));//否则输出查询到的最小可能值
			putchar('\n');
		}
	}
	system("pause");
	return 0;
}