大致题意：
给定一张无向图(G(V,E))，(q)次询问(u,v)之间求找到一条路径使得路径上的最小权值最大。若不连通，输出(-1)。
(n leq 10^4,mleq 5*10^4,qleq 3*10^4)
Solution
考虑到在(m)条边中，并不是所有的边都一定有机会被经过。什么意思呢？参考Kruskal最小生成树算法的思想，那些连接着（已经被更小边完成连通的两点）的边，一定不在最小生成树中。
这道题要求路径最小值最大，于是我们就把边按照边权从大到小排序并建立最大生成树。
建立了之后，两点之间就有了唯一一条路径，并且这是在一棵树上，需要完成的操作为求两点路径间的最小值。
于是考虑((u,v))之间一定为(u→lca(u,v)→v)这样一条路径。看到(LCA)狂喜想到倍增。
在预处理的时候顺便处理一下每个点到自己(2^k)级祖先路径上的最小值，在跳(LCA)的时候使用即可。
对于一组询问((u,v))，我们就先判断它们是否连通，可以利用求最大生成树时的并查集来查询。
然后在跳(LCA)的过程中，每次跳边之前优先利用预处理的倍增最小值数组更新答案，原本返回(LCA)编号的地方改为返回答案即可。
另外，虽然数据水，直接从任意结点搜一次可以通过，但是实际上正确性是有点问题的。因为图不保证完全连通，可能形成多棵树，于是加个(vis)标记多搜几次就好了，虽然在水数据下不会有啥变化。
code:
#include<bits/stdc++.h>
using namespace std;
const int N=20020;
const int M=100010;
struct node
{
int u,v,w;
}g[M];
int fa[N];
bool vis[N];
inline int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);}
inline bool merge(int u,int v)
{
int r1=get(u),r2=get(v);
if(r1==r2)return 0;
fa[r1]=r2;
return 1;
}
inline bool cmp(node a,node b)
{
return a.w>b.w;
}
int head[M],to[M],val[M],nxt[M],cnt;
int lg[N];
void add(int u,int v,int w)
{
cnt++;
to[cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
int dep[N],f[N][26],mn[N][26];
void dfs(int u,int F,int w)
{
vis[u]=1;
dep[u]=dep[F]+1;
f[u][0]=F;
mn[u][0]=w;
for(int i=1;(1<<i)<=dep[u];i++)
f[u][i]=f[f[u][i-1]][i-1],
mn[u][i]=min(mn[u][i-1],mn[f[u][i-1]][i-1]);
for(int i=head[u];i;i=nxt[i])
if(to[i]!=F)dfs(to[i],u,val[i]);
}
int lca(int x,int y)
{
int mini=0x3f3f3f3f;
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])
{
mini=min(mini,mn[x][lg[dep[x]-dep[y]]]);
x=f[x][lg[dep[x]-dep[y]]];
}
if(x==y)return mini;
for(int k=lg[dep[x]];k>=0;k--)
if(f[x][k]!=f[y][k])
{
mini=min(mini,min(mn[x][k],mn[y][k]));
x=f[x][k],y=f[y][k];
}
mini=min(mini,min(mn[x][0],mn[y][0]));
return mini;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i,lg[i]=lg[i-1]+(1<<lg[i-1]==i);
for(int i=1;i<=n;i++)lg[i]--;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&g[i].u,&g[i].v,&g[i].w);
sort(g+1,g+1+m,cmp);
int tot=0;
for(int i=1;i<=m;i++)
{
if(merge(g[i].u,g[i].v))
add(g[i].u,g[i].v,g[i].w),
add(g[i].v,g[i].u,g[i].w),
tot++;
if(tot==n-1)break;
}
for(int i=1;i<=n;i++)
if(!vis[i])dfs(i,0,0);
int t;
scanf("%d",&t);
while(t--)
{
int u,v;
scanf("%d%d",&u,&v);
if(get(u)!=get(v))
{
puts("-1");
continue;
}
printf("%d
",lca(u,v));
}
return 0;
}