我是可莉的狗

loj 瓶颈路模板拿这个过了

建了双向边也倒序 dfs 了，不是很懂

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
int n,m;

int u,v,w;
struct n0de{
	int u,v,w;
}g[2145141];
bool cmp(n0de a,n0de b){return a.w<b.w;}
int k;
int p[2145141];
int find(int x){
	while(x!=p[x]) {
		x=p[x]=p[p[x]];
	}
	return x;
}
int val[2145141];

int tot;
vector <int> edge[2145141];
void kruskal(){
	for(int i=1;i<=2*n+10;i++){
		p[i]=i;
	}
	tot=n;
	for(int i=1;i<=m;i++){
		int u=find(g[i].u),v=find(g[i].v);
		if(u!=v){
			p[u]=p[v]=++tot;
			edge[u].push_back(tot);
			edge[v].push_back(tot);
			edge[tot].push_back(u);
			edge[tot].push_back(v);
			val[tot]=g[i].w;
		}
	}
}
int siz[2145141],dep[2145141],son[2145141],fa[2145141],top[2145141];
void dfs1(int u,int f){
	siz[u]=1;
	dep[u]=dep[f]+1;
	fa[u]=f;
	for(auto e:edge[u]){
		if(e==f) continue;
		dfs1(e,u);
		siz[u]+=siz[e];
		int maxson=-1;
		if(maxson<siz[e]){
			maxson=siz[e];
			son[u]=e;
		}
	}
}
void dfs2(int u,int t){
	top[u]=t;
	if(son[u]==0) return ;
	dfs2(son[u],t);
	for(auto e:edge[u]){
		if(e==fa[u] or e==son[u]) continue;
		dfs2(e,e);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) return v;
	else return u;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>g[i].u>>g[i].v>>g[i].w;
	}
	sort(g+1,g+m+1,cmp);
	kruskal();
	for(int i=tot;i;i--){
		if(dep[i]==0){
			dep[i]=1;
			dfs1(i,0),dfs2(i,i);
		}
	}
	cin>>k;
	while(k--){
		cin>>u>>v;
		if(find(u)!=find(v)) cout<<"impossible"<<'\n';
		else cout<<val[lca(u,v)]<<'\n';
	}
	return 0;
}