LCA+最小生成树

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,m,x,y,z,fa[N],sum,ans;
struct nod{
	int u,v,w;
}e[N];
struct no{
	int to,w,ne;
}tr[N];
bool cmp(nod x,nod y){
	return x.w<y.w;
}
int head[N],tot=-1,f[N][25],p[N][25],d[N],maxh,q;
void add(int x,int y,int z){
	tr[++tot].to=y;
	tr[tot].w=z;
	tr[tot].ne=head[x];
	head[x]=tot;
}
void dfs(int x,int fa,int dep){
	for(int i=head[x];i!=-1;i=tr[i].ne){
		int v=tr[i].to;
		if(v==fa)continue;
		f[v][0]=x,d[v]=d[x]+1,p[v][0]=tr[i].w;
		dfs(v,x,dep+1);
	}
}
int LCA(int x,int y){
	if(d[x]<d[y])swap(x,y);
	int xx=0,yy=0;
	for(int i=maxh;i>=0;i--){
		if(d[f[x][i]]>=d[y])x=f[x][i],xx=max(xx,p[x][i]);
	}
	if(x==y)return x;
	for(int i=maxh;i>=0;i--){
		if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i],yy=max(yy,p[y][i]),xx=max(xx,p[x][i]);
	}
	return max(max(xx,yy),p[x][0]);
}
int fi(int x){
	if(fa[x]==x)return x;
	return fa[x]=fi(fa[x]);
}
int main(){
	memset(head,-1,sizeof head);
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=e[i].u,y=e[i].v,z=e[i].w;
		int xx=fi(x),yy=fi(y);
		if(xx!=yy){
			fa[xx]=yy;
			add(x,y,z);
			add(y,x,z);
		}
	}
	d[1]=1;
	maxh=log(n)/log(2);
	dfs(1,0,1);
	for(int i=1;i<=maxh;i++)
		for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1],p[j][i]=max(p[j][i-1],p[f[j][i-1]][i-1]);
	cin>>q;
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>a>>b;
		if(fi(a)!=fi(b)){
			cout<<"impossible\n";
			continue;
		}
		cout<<LCA(a,b)<<'\n';
	}
	return 0;
}