题目描述
AA国有nn座城市，编号从 11到nn，城市之间有 mm 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 qq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

输入格式
第一行有两个用一个空格隔开的整数n,mn,m，表示 AA 国有nn 座城市和 mm 条道路。

接下来 mm行每行33个整数 x, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx号城市到yy号城市有一条限重为 zz 的道路。注意： ** xx 不等于 yy，两座城市之间可能有多条道路 ** 。

接下来一行有一个整数 q，表示有 q 辆货车需要运货。

接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： ** x 不等于 y ** 。

输出格式
共有 qq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货车不能到达目的地，输出-1−1。

输入输出样例
输入 #1复制
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出 #1复制
3
-1
3
说明/提示
对于 30%30%的数据，0 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000；

对于 60%60%的数据，0 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000；

对于 100%100%的数据，0 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。

其实完全可以求最大生成树，然后lca倍增。

但是这道题还有什么意思呢？

这道题就是让我们求出任意两点任意路径的最小边权的最大值。

于是可以用kruskal重构树来写。

很经典的Kruskal重构树应用—求图中任意两点间所有路径中最小边权的最大值
在kruskal的过程中
若当前边所连两点u和v不在一个集合内
则新建一个节点node，点权为该边边权
然后连接u所在集合的根与node以及v所在集合的根与node
重构完成之后，指定每个集合的根作为所在森林的根
则u到v路径上最大边权的最小值 就是LCA(u,v)的点权

要注意，题目可能是森林。

AC代码：

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