Problem 树上倍增
题目大意
给出一个图，给出若干个点对u,v，求u,v的一条路径，该路径上最小的边权值最大。
Solution
看到这个题第一反应是图论。。
然而，任意路径最小的边权值最大，如果仔细思考的话就会知道，如果两个点相互连通，那么一定走的是最大生成树上的路径，而不会选择其他任何一条路径去走。
这个是可以非常简单证明的，就不再详述。
那么既然知道了这个，当然是先建一颗最大生成树啦！
现在问题来了，Prim&Kruskal，选哪个？
分析一下，prim复杂度$O(n^2)$,n为总点数。
Kruskal复杂度$O(m\log_2n)$,m为总边数。
显而易见，在这一道题目中kruskal更优。
于是写一个kruskal最大生成树。
接下来要在这颗树上跑。
我们设立一个fa数组，其fa[i][j]表示对于i节点，向上的2^j个节点编号是什么。显而易见，fa[i][0]就是i的父亲。
$$fa[i][j]=fa[fa[i][j-1][j-1]$$
然后我们还需要一个储存最小值的数组，设立minn数组，其中minn[i][j]表示对于i节点，向上2^j个节点的边最小值
显而易见，minn[i][0]就表示i节点本身链接父亲边的权值.
$$minn[i][j]=\min(minn[fa[i][j-1]][j-1],minn[i][j-1])$$
可以看出，这两个数组在O(n)的时间就可以求出来了。
接下来，对于每一个询问点对，我们只需要倍增求lca，再求两个点到lca路径上最小值，就可以求出答案。
判断uv谁深度更深，更深深度先跳到同一深度。
接下来两个一起向上跳，能够跳就跳。
具体方法可以看代码。
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct kruskal{
int u,v,w;
}ekr[];
struct node{
int to,next,w;
}e[];
int f[],h[],dep[],n,m,u,v,w,q,ktot=,tot=,ans;
int fa[][],minn[][];
void add_kruskal(int u,int v,int w){
ekr[++ktot].u=u;ekr[ktot].v=v;ekr[ktot].w=w;
}
bool cmp(kruskal a,kruskal b){
return a.w>b.w;
}
void add(int u,int v,int w){
e[++tot].to=v;e[tot].next=h[u];h[u]=tot;e[tot].w=w;
e[++tot].to=u;e[tot].next=h[v];h[v]=tot;e[tot].w=w;
}
void initdfs(int x,int last,int we,int depth){
dep[x]=depth;
fa[x][]=last;
minn[x][]=we;
for(int i=;i<=;i++){
fa[x][i]=fa[fa[x][i-]][i-];
minn[x][i]=min(minn[x][i-],minn[fa[x][i-]][i-]);
}
for(int i=h[x];~i;i=e[i].next)
if(e[i].to!=last)initdfs(e[i].to,x,e[i].w,depth+);
}
void queue(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int dist=dep[u]-dep[v],tmp=;
while(dist){
if(dist%==)ans=min(ans,minn[u][tmp]),u=fa[u][tmp];
tmp++;
dist>>=;
}
for(int i=;i>=;i--){
if(fa[u][i]!=fa[v][i]){
ans=min(min(ans,minn[u][i]),minn[v][i]);
u=fa[u][i];
v=fa[v][i];
}
}
ans=(u==v)?ans:min(min(ans,minn[u][]),minn[v][]);
}
int find(int x){
if(f[x]!=x)f[x]=find(f[x]);
return f[x];
}
int main(){
// freopen("xsy2018.in","r",stdin);
memset(h,-,sizeof(h));
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add_kruskal(u,v,w);
}
sort(ekr+,ekr+ktot+,cmp);
for(int i=;i<=n;i++)f[i]=i;
for(int i=,sum=;i<=ktot;i++){
int fu=find(ekr[i].u),fv=find(ekr[i].v);
if(fu!=fv){
add(ekr[i].u,ekr[i].v,ekr[i].w);
f[fu]=fv;f[ekr[i].u]=fv;f[ekr[i].v]=fv;
sum++;
}
if(tot==((n-)<<))break;
}
initdfs(,,,);
scanf("%d",&q);
for(int i=;i<=q;i++){
scanf("%d%d",&u,&v);
ans=;
queue(u,v);
printf("%d\n",(ans==)?-:ans);
}
}