题目：Bond
题意：给出一张无向图和m个询问x y，输出x，y之间的最小瓶颈路。
思路：用lca倍增求最小瓶颈路。
注意：当x和y的lca是y时要特判。
代码：
#include<bits/stdc++.h>
using namespace std;#define maxn 50000
#define maxm 100000
#define maxl 20struct Edge {int x,y,z;Edge(int xx=0,int yy=0,int zz=0) {x=xx,y=yy,z=zz;}bool operator < (const Edge& oth) const {return z<oth.z||(z==oth.z&&(x<oth.x||(x==oth.x&&y<oth.y)));}
};struct Node {int fa,c,d;
};int n,m;
Edge a[maxm+5];
int fa[maxm+5];vector<Edge> tr[maxn+5];Node e[maxn+5];int anc[maxn+5][maxl+5];
int mc[maxn+5][maxl+5];void init() {for(int i=1; i<=maxm; i++) fa[i]=i;for(int i=1; i<=maxn; i++) tr[i].clear();memset(mc,0,sizeof(mc));memset(anc,0,sizeof(anc));
}void readin() {for(int i=1; i<=m; i++) {scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);}
}int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);
}int kruskal() {int ans=0,cnt=0;for(int i=1; i<=m; i++) {int fa1=find(a[i].x),fa2=find(a[i].y);if(fa1==fa2) continue;fa[fa1]=fa2;ans+=a[i].z;cnt++;tr[a[i].x].push_back(a[i]);tr[a[i].y].push_back(Edge(a[i].y,a[i].x,a[i].z));if(cnt==n-1) break;}return ans;
}void chg(int x,int fa,int d) {e[x].fa=fa,e[x].d=d;for(int i=0; i<tr[x].size(); i++) {int y=tr[x][i].y;if(y!=fa) e[y].c=tr[x][i].z,chg(y,x,d+1);}return ;
}int query(int x,int y) {int p;for(p=1; (1<<p)<=e[x].d; p++);p--;int ans=-(1<<30);for(int i=p; i>=0; i--) {if(e[x].d>=(1<<i)+e[y].d) {ans=max(ans,mc[x][i]);x=anc[x][i];}}if(x==y) return ans;for(int i=p; i>=0; i--) {if(anc[x][i]&&anc[x][i]!=anc[y][i]) {ans=max(ans,mc[x][i]),ans=max(ans,mc[y][i]);x=anc[x][i],y=anc[y][i];}}ans=max(ans,e[x].c),ans=max(ans,e[y].c);return ans;
}void slv() {int q;scanf("%d",&q);while(q--) {int x,y;scanf("%d%d",&x,&y);if(e[x].d<e[y].d) swap(x,y);printf("%d\n",query(x,y));}
}void mk() {for(int i=1; i<=n; i++) {anc[i][0]=e[i].fa;mc[i][0]=e[i].c;}for(int j=1; (1<<j)<n; j++) {for(int i=1; i<=n; i++) {if(anc[i][j-1]) {anc[i][j]=anc[anc[i][j-1]][j-1];mc[i][j]=max(mc[i][j-1],mc[anc[i][j-1]][j-1]);}}}
}int main() {int T=0;while(~scanf("%d%d",&n,&m)) {if(T) printf("\n");else T=1;init();readin();sort(a+1,a+m+1);int s=kruskal();chg(1,1,0);mk();slv();}return 0;
}