题意
??给定无向带权的Graph=（V，E）
??现在有Q组询问：u 到v的所有路径的最小的最大边权
解法
树链剖分：
一开始看到最小的最大边权，我还往二分上想……复杂度O（Q?nlogn ），直接T飞
然后认真想了想，其实啊，这有一个很明显的结论：最小的最大边权必定是最小生成树上的边的边权
要证明也很容易，网上应该搜的到，这里就不证明了
所以就种一棵最小生成树，然后就是要求树上两点的路径上的最大边权，想到什么了呢？……树链剖分！
然后就套用一个树链剖分的模板，就可以logn 的解决每一次询问
复杂度
O（|E|log|E|+Qlog|V|）
代码
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#define ls 2*k
#define rs 2*k+1
#define Rint register int
#define Lint long long int
using namespace std;
const int INF=0x3f3f3f3f;
const int E=100010;
const int N=50010;
struct Edge
{int u,v,w;bool operator < (const Edge &a) const{return w<a.w;}
}e[E];
struct tree
{int l,r;int v;
}T[N*4];
struct node
{int next,to,w;
}t[E];
int son[N],siz[N],top[N];
int head[N],w[N],dep[N];
int dfn[N],dfnm[N],f[N];
int fa[N];
int n,m,q,num,cnt;
void mem()
{memset( fa,0x0,sizeof fa );memset( son,0x0,sizeof son );memset( head,0x0,sizeof head );
}
void add(int u,int v,int w)
{t[++num]=(node){ head[u],v,w };head[u]=num;
}
int find(Rint x)
{return x==f[x] ? f[x] : f[x]=find( f[x] );
}
int max(int x,int y)
{return x>y ? x:y ;
}
void Tarjan(Rint k)
{siz[k]=1;for(Rint i=head[k],x; i ;i=t[i].next){x=t[i].to;if( fa[x] ) continue ;dep[x]=dep[k]+1,fa[x]=k;Tarjan( x );siz[k]+=siz[x];if( siz[x]>siz[son[k]] || !son[k] ) son[k]=x;}
}
void dfs(Rint k,Rint fa)
{dfn[k]=++cnt;dfnm[cnt]=k;if( son[k] ){top[son[k]]=top[k];dfs( son[k],k );}for(Rint i=head[k],x; i ;i=t[i].next){x=t[i].to;if( x!=fa ) w[x]=t[i].w;if( x==fa || x==son[k] ) continue ;top[x]=x,dfs( x,k );}
}
void build(int k,int l,int r)
{T[k].l=l,T[k].r=r;if( l==r ){T[k].v=w[dfnm[l]];return ;}int mid=(l+r)/2;build( ls,l,mid ),build( rs,mid+1,r );T[k].v=max( T[ls].v,T[rs].v );
}
int query(Rint k,Rint l,Rint r)
{if( l>r ) return 0;if( T[k].l==l && T[k].r==r ) return T[k].v;if( r<=T[ls].r ) return query( ls,l,r );elseif( l>=T[rs].l ) return query( rs,l,r );else{int x=query( ls,l,T[ls].r ),y=query( rs,T[rs].l,r );return max( x,y );}
}
int ask(int u,int v)
{Rint ret=0;while( top[u]!=top[v] ){if( dep[top[u]]<dep[top[v]] ) swap( u,v );ret=max( ret,query( 1,dfn[top[u]],dfn[u] ) );u=fa[top[u]];}if( dep[u]>dep[v] ) swap( u,v );ret=max( ret,query( 1,dfn[u]+1,dfn[v] ) );return ret;
}
void Kruskal()
{int u,v;sort( e+1,e+cnt+1 );for(int i=1;i<=m;i++){u=e[i].u,v=e[i].v;if( find( u )==find( v ) ) continue ;add( u,v,e[i].w ),add( v,u,e[i].w );f[find( u )]=find( v );}
}
int main()
{int u,v,w,C=0;while( scanf("%d%d",&n,&m)!=EOF ){if( ++C>1 ) printf("\n");cnt=num=0;mem();for(int i=1;i<=n;i++) f[i]=i;for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);e[++cnt]=(Edge){ u,v,w };}Kruskal(),cnt=0;fa[1]=1;dep[1]=1,Tarjan( 1 );top[1]=1,dfs( 1,0 );build( 1,1,n );scanf("%d",&q);while( q-- ){scanf("%d%d",&u,&v);printf("%d\n",ask( u,v ));}}return 0;
}