星际导航

题目描述
\text{sideman}sideman 做好了回到 \text{Gliese}Gliese 星球的硬件准备，但是 \text{sideman}sideman 的导航系统还没有完全设计好。为了方便起见，我们可以认为宇宙是一张有 NN 个顶点和 MM 条边的带权无向图，顶点表示各个星系，两个星系之间有边就表示两个星系之间可以直航，而边权则是航行的危险程度。

\text{sideman}sideman 现在想把危险程度降到最小，具体地来说，就是对于若干个询问 (A, B)(A,B)，\text{sideman}sideman 想知道从顶点 AA 航行到顶点 BB 所经过的最危险的边的危险程度值最小可能是多少。作为 \text{sideman}sideman 的同学，你们要帮助 \text{sideman}sideman 返回家园，兼享受安全美妙的宇宙航行。所以这个任务就交给你了。

输入格式
第一行包含两个正整数 NN 和 MM，表示点数和边数。

之后 MM 行，每行三个整数 AA，BB 和 LL，表示顶点 AA 和 BB 之间有一条边长为 LL 的边。顶点从 11 开始标号。

下面一行包含一个正整数 QQ，表示询问的数目。

之后 QQ 行，每行两个整数 AA 和 BB，表示询问 AA 和 BB 之间最危险的边危险程度的可能最小值。

输出格式
对于每个询问， 在单独的一行内输出结果。如果两个顶点之间不可达， 输出 \text{impossible}impossible。

输入输出样例
输入 #1复制
4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2
输出 #1复制
5
4
5

求两点间最大边权的最小值，kruskal重构树即可。

建立最小生成树。

若最小边权最大值则最大生成树。

求LCA树剖即可，比较快。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,q,son[N],f[N],fa[N<<1],sz[N],vis[N],h[N],bl[N],val[N];
int head[N],nex[N<<1],to[N<<1],tot;
struct node{int u,v,w;}t[N*3];
int cmp(node a,node b){return a.w<b.w;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void dfs1(int x){
	sz[x]=1; vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(f[x]==to[i])	continue;
		f[to[i]]=x; h[to[i]]=h[x]+1;
		dfs1(to[i]); sz[x]+=sz[to[i]];
		if(sz[to[i]]>sz[son[x]]) son[x]=to[i];
	}
}
void dfs2(int x,int belong){
	bl[x]=belong;
	if(!son[x])	return ; dfs2(son[x],belong);
	for(int i=head[x];i;i=nex[i])
		if(h[to[i]]>h[x]&&to[i]!=son[x])	dfs2(to[i],to[i]);
}
inline int lca(int x,int y){
	while(bl[x]^bl[y]){
		if(h[bl[x]]<h[bl[y]])	swap(x,y);	x=f[bl[x]];
	}
	return (h[x]>h[y]?val[y]:val[x]);
}
void ex_kruskal(){
	int idx=n; sort(t+1,t+1+m,cmp);
	for(int i=1;i<=n;i++)	fa[i]=i;
	for(int i=1;i<=m;i++){
		int fx=find(t[i].u),fy=find(t[i].v);
		if(fx!=fy){
			val[++idx]=t[i].w; fa[fx]=fa[fy]=fa[idx]=idx;
			add(idx,fx),add(idx,fy),add(fx,idx),add(fy,idx);
			if(idx==n*2-1)	break;
		}
	}
	for(int i=1;i<=idx;i++){
		if(vis[i])	continue;
		int fa=find(i); dfs1(fa); dfs2(fa,fa);
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)	scanf("%d %d %d",&t[i].u,&t[i].v,&t[i].w);
	cin>>q; ex_kruskal();
	while(q--){
		int a,b;	scanf("%d %d",&a,&b);
		if(find(a)!=find(b))	puts("impossible");
		else	printf("%d\n",lca(a,b));
	}
	return 0;
}