题目
题解

Solution

首先如果这道题是可以离线的，那么我们可以将边从小到大排序，每次加边，然后把两个端点所在的联通块并在一起。那么当 A A A， B B B刚好联通时加的那条边的边权就是答案。但是本题强制在线，所以我们必须先预处理再回答询问。
我们按照 k r u s k a l kruskal kruskal求最小生成树的方式加边，但每次在加边时，新建一个节点，然后把两个联通块（其实是两棵二叉树）的根节点作为其左右儿子，把边权赋值给新建节点。那么我们可以发现这棵树有几个性质。

1.是一棵二叉树（虽然这道题并没有什么卵用）；
2.满足父节点的值大于等于儿子节点，是一个大顶堆，这是最关键的一点；
3.原图上任意两点间路径最长边的最小值等于其 l c a lca lca的值；
这种建树的方法称作 k r u s k a l kruskal kruskal重构树。
那么 A A A， B B B的 l c a lca lca就是所求答案。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=15001;
int dep[N],fa[N<<1],n,m,k,i,f[N<<1][15],cnt,u,v,ch[N<<1][2],val[N<<1],j;
struct node{
	int x,y,w;
}e[N<<2];
inline char gc(){
	static char buf[100000],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int x=0,fl=1;char ch=gc();
	for (;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;
	for (;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);
	return x*fl;
}
inline void wri(int a){if(a<0)a=-a,putchar('-');if(a>=10)wri(a/10);putchar(a%10|48);}
inline void wln(int a){wri(a);puts("");}
bool cmp(node a,node b){return a.w<b.w;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int lca(int x,int y){
	if (dep[x]<dep[y]) swap(x,y);
	for (int i=14;~i;i--)
		if (dep[f[x][i]]>=dep[y]) x=f[x][i];
	if (x==y) return x;
	for (int i=14;~i;i--)
		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main(){
	n=rd(),m=rd(),k=rd();cnt=n;
	for (i=0;i<m;i++) e[i].x=rd(),e[i].y=rd(),e[i].w=rd();
	sort(e,e+m,cmp);
	for (i=1;i<2*n;i++) fa[i]=i;
	for (i=0;i<m;i++){
		u=e[i].x;v=e[i].y;
		if (find(u)==find(v)) continue;
		ch[++cnt][0]=fa[u];ch[cnt][1]=fa[v];
		fa[fa[u]]=fa[fa[v]]=f[fa[u]][0]=f[fa[v]][0]=cnt;
		val[cnt]=e[i].w;
	}
	for (i=cnt;i>=n;i--) dep[ch[i][0]]=dep[ch[i][1]]=dep[i]+1;
	dep[0]=-1;
	for (j=1;j<15;j++)
		for (i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1];
	for (;k--;) wln(val[lca(rd(),rd())]);
}