帮帮孩子吧，孩子快疯了

提交记录

感谢大佬/bx/bx/bx

代码:

#include <bits/stdc++.h>
using namespace std;
//if you wanna use pbds,please open \
Dev-Cpp\MinGW64\lib\gcc\x86_64-w64-mingw32\4.9.2\include\c++\x86_64-w64-mingw32\bits\extc++.h
//to find the lib names
//and open the code under this code
//using namespace __gnu_pbds;
//This is a O(1) copy list\
#include <ext/rope>\
using namespace __gnu_cxx;
namespace MySpace{
	#define max(a,b) (([](auto ta,auto tb){return ta>tb?ta:tb;})((a),(b)))
	#define min(a,b) (([](auto ta,auto tb){return ta<tb?ta:tb;})((a),(b)))
	#define lowbit(x) (x&(-x))
	#ifdef ONLINE_JUDGE
	#define getchar getchar_unlocked
	#endif
	template <typename T>
	inline T read(){
		T now=0,nev=1;
		char c=getchar();
		while(c<'0' || c>'9') {
			if(c=='-') nev=-1;
			c=getchar();
		}
		while(c>='0' && c<='9') now=(now<<1)+(now<<3)+(c&15),c=getchar();
		return now*nev;
	}
	template<typename T>
	T qpow(T a,T n,T p){
		T res=1;
		while (n){
			if (n&1) res=1ll*res*a%p;
			a=1ll*a*a%p;
			n>>=1;
		}
		return res;
	}
	template<typename T>
	T gcd(T a,T b){return (b>0?gcd(b,a%b):a);}
}
using namespace MySpace;
#define int long long
//const int INF=0x66CCFF66;
const int maxn=1e5+5;
using ll=long long;
int n,m;
//一个简单的边结构体 
struct edge{int u,v;ll w;bool operator<(const edge tmp)const{return w<tmp.w;}};
vector<edge> e;
//两个简单的并查集 
int bcj[maxn];
int fd(int x){return bcj[x]==0?x:bcj[x]=fd(bcj[x]);}
void hb(int x,int y){if (fd(x)!=fd(y)) bcj[fd(y)]=fd(x);return;}

int bcjb[maxn];//这个记录重构树根节点
int fdb(int x){return bcjb[x]==0?x:bcjb[x]=fd(bcjb[x]);}
void hbb(int x,int y){if (fd(x)!=fd(y)) bcjb[fd(y)]=fd(x);return;}
//Kruskal rebuild tree
int val[maxn<<1],tot=n;
int fa[maxn<<1],dep[maxn<<1];
void Kruskal(){
	stable_sort(e.begin(),e.end());//排序 
	int cnt=1,ptr=0;//记录已经加入的边的个数 
	while (cnt<n && ptr<=m){//如果还有点没有加入并且没有找完所有边 
		edge tmpe=e[ptr];//找到当前点 
		int u=tmpe.u,v=tmpe.v;//记录u v 
		ll w=tmpe.w;//记录w 
		if (fd(u)!=fd(v)){//如果还未加入集合 
			hb(u,v);//合并 
			val[++tot]=w;//找到新点，点权定为边权 
			int fau=fdb(u),fav=fdb(v);
			hbb(tot,fau);hbb(tot,fav);
			fa[tot]=fa[fau]=fa[fav]=tot;//记录所有的这些的父亲 
			dep[tot]=max(dep[fau],dep[fav])+1;//记录深度 
			dep[fau]=dep[fav]=dep[tot]-1;//更新深度 
			cnt++;//将已经找到的点++ 
		}
		ptr++;//找下一个边 
	}
	return;
}
int query(int u,int v){
	if (dep[u]>dep[v]) swap(u,v);//选择较低的点作为u 
	return val[fa[v]];//返回答案 
}
signed main(){
	n=read<int>(),m=read<int>();
	for (int i=1;i<=n;i++) fa[i]=i;//记录fa 
	for (int i=1;i<=m;i++){
		int u=read<int>(),v=read<int>();
		ll w=read<ll>();
		e.push_back({u,v,w});//放入边 
	}
	Kruskal();//建树 
	int q=read<int>();
	while (q--){
		int u=read<int>(),v=read<int>();
		if (fd(u)!=fd(v)) {//如果无法到达就imp 
			puts("impossible");
			continue;
		}
		printf("%lld\n",query(u,v));//不然取得结果并输出 
	}
	return 0;
}