Kruskal重构树板子

//2024-11-26 20:45:49
#include<bits/stdc++.h>
#define db double
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
bool MBE;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f; 
}
const int mxn=2e5+10;
int val[mxn],f[mxn][21],fa[mxn];
int n,m,cnt,dep[mxn];
struct node{
	int u,v,w;
}e[300010];
vector<int>E[mxn];
bool cmp(node x,node y){
	return x.w<y.w;
}
void dfs(int u,int ff){
	dep[u]=dep[ff]+1;
	f[u][0]=ff;
	for(int i=1;i<=20;i++)
		f[u][i]=f[f[ff][i-1]][i-1];
	for(int v:E[u])
		dfs(v,u);
}
int LCA(int u,int v){
	if(u==v)return u;
	if(dep[u]<dep[v])swap(u,v);
	for(int i=20;i>=0;i--)
		if(dep[f[u][i]]>=dep[v])u=f[u][i];
	if(u==v)return u;
	for(int i=20;i>=0;i--)
		if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
	return f[u][0];
}
int find(int x){
	if(fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    	e[i]=(node){read(),read(),read()};
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=n*2;i++)
    	fa[i]=i;
    cnt=n;
    for(int i=1;i<=m;i++){
    	int u=e[i].u,v=e[i].v,w=e[i].w;
    	u=find(u),v=find(v);
    	if(u==v)continue;
    	fa[u]=fa[v]=++cnt;
    	val[cnt]=w;
    	E[cnt].eb(u),E[cnt].eb(v);
    	// cout<<cnt<<" "<<u<<" "<<v<<endl;
    }
    for(int i=cnt;i>=1;i--)
    	if(!dep[i])dfs(i,0);
    int q=read();
    while(q--){
    	int u=read(),v=read();
    	if(find(u)!=find(v))puts("impossible");
    	else printf("%lld\n",val[LCA(u,v)]);
    }
    bool MED;
    cerr<<(&MED-&MBE)/1048576.0<<" MB, "<<1000*clock()/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}