给你N个点的无向图 (1 <= N <= 15,000)，记为：1…N。
图中有M条边 (1 <= M <= 30,000) ，第j条边的长度为： d_j ( 1 < = d_j < = 1,000,000,000).
现在有 K个询问 (1 < = K < = 20,000)。
每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int N=1e5+10,INF=1e9,B=19;
4 inline int read(){
5 char c=getchar();int x=0,f=1;
6 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
7 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
8 return x*f;
9 }
10 int fa[N],f[N][21],ch[N][21],cnt,val[N],dep[N];
11 int n,M,K;
12
13 struct Edge{
14 int u,v,w;
15 bool operator< (const Edge &rhs) const {
16 return w<rhs.w;
17 }
18 }E[N];
19 int num=0;
20
21 inline void add(int x,int y,int z){
22 E[++num]=(Edge){x,y,z};
23 }
24
25 int find(int x){
26 if(fa[x]==x) return fa[x];
27 else return fa[x]=find(fa[x]);
28 }
29
30 void Kruskal(){
31 sort(E+1,E+num+1);//按边的权值排序
32 int tot=0;
33 for(int i=1;i<=M;i++){
34 int x=E[i].u,y=E[i].v;
35 int fx=find(x),fy=find(y);
36 if(fx!=fy){//建树
37 ch[++cnt][0]=fx,ch[cnt][1]=fy;
38 fa[fa[x]]=fa[fa[y]]=f[fa[x]][0]=f[fa[y]][0]=cnt;
39 val[cnt]=E[i].w;//边权转化为点权
40 }
41 }
42 }
43
44 void dfs(int x){//求深度
45 if(!ch[x][0]&&!ch[x][1]) return ;//叶子节点
46 dep[ch[x][0]]=dep[ch[x][1]]=dep[x]+1;
47 dfs(ch[x][0]);dfs(ch[x][1]);
48 }
49
50 int LCA(int x,int y){//倍增求LCA
51 if(dep[x]<dep[y]) swap(x,y);
52 for(int i=B;i>=0;i--){
53 if(dep[f[x][i]]>=dep[y])
54 x=f[x][i];
55 }
56 if(x==y) return x;
57 for(int i=B;i>=0;i--){
58 if(f[x][i]!=f[y][i])
59 x=f[x][i],y=f[y][i];
60 }
61 return f[x][0];
62 }
63
64 main(){
65 cnt=n=read();M=read();K=read();
66 for(int i=1;i<=n<<1;i++) fa[i]=i;//初始化
67 for(int i=1;i<=M;i++){
68 int x=read(),y=read(),z=read();
69 add(x,y,z);
70 }
71 Kruskal();//重构树
72 dep[cnt]=1;dfs(cnt);//cnt重构完后所有的节点数,也是当前的根节点
73 for(int i=1;i<=B;i++){
74 for(int j=1;j<=2*N;j++)
75 f[j][i]=f[f[j][i-1]][i-1];//ST表
76 }
77 while(K--){
78 int x=read(),y=read();
79 cout<<val[LCA(x,y)]<<endl; //答案就是x，y最近公共祖先的点权
80 }
81 return 0;
82 }
