Problem
题目大意：
给定一个 (n) 个点 (m) 条边的无向图，不保证连通，边有权值。有 (q) 次询问，每次询问从 (u) 到 (v) 的路径中边权最小的边的最大值。
Solution
首先，观察题目，可以满足条件的路径一定在整个图的最大生成树上。
更准确的说，是在整个图的“最大瓶颈生成树”上，也就是这个生成树上最小的边最大。
显然这是正确的，可以从它的定义上来理解。
那么我们首先求出图的“最大瓶颈生成树”。由于这是一棵树，所以两点之间的路径是唯一的，求出这条路径的最小的边权即可。
对于处理边权，我们可以使用树剖。
常用的方法是在第一遍预处理之后枚举所有的边，将边权放到深度较低的点上。
但是此时，在处理链上信息时，两点的 LCA 上的信息是不该被记录的。
原来的代码应该长这个亚子：
int query_path(int x,int y)
{
int res=1e9;
while(top[x]!=top[y])
{
if(depth[top[x]]<depth[top[y]]) swap(x,y);
res=min(res,query(id[top[x]],id[x]));
x=fa[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
res=min(res,query(id[x],id[y]));
return res;
}
在最后的数据更新，即res=min(res,query(id[x],id[y]));中，(x=LCA(x,y))，所以此时只要把这句话改成res=min(res,query(id[x]+1,id[y]));即可。
然后还有一个问题就是，图是不连通的，所以预处理 dfs 的时候要注意对每个树都处理一下。然后用并查集维护连通性就行了。
另外，因为是静态查询（边权不变），所以可以用 ST 表来维护。
还有一个注意点放代码里了。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 10005
#define MAXM 50005
using namespace std;
int n,m,q;
struct node{int u,v,w;}a[MAXM];
bool cmp(node x,node y){return x.w>y.w;}
struct bin
{
int f[MAXN];
bin()
{
for(int i=0;i<MAXN;i++) f[i]=i;
return ;
}
int find(int x){return (f[x]==x?x:f[x]=find(f[x]));}
bool query(int x,int y){return find(x)==find(y);}
void add(int x,int y){f[find(x)]=find(y);return ;}
}b;//并查集
struct graph
{
int tot;
int hd[MAXN];
int nxt[MAXN*2],to[MAXN*2],dt[MAXN*2];
void add(int u,int v,int w)
{
nxt[++tot]=hd[u];
hd[u]=tot;
to[tot]=v;
dt[tot]=w;
return ;
}
}g;//链式前向星
int fa[MAXN],depth[MAXN],size[MAXN],son[MAXN];
int cnt,top[MAXN],id[MAXN],w[MAXN];
int lg[MAXN],Min[MAXN][25];
void dfs1(int now,int F)
{
fa[now]=F;size[now]=1;
depth[now]=depth[fa[now]]+1;
for(int i=g.hd[now];i;i=g.nxt[i])
if(g.to[i]!=fa[now])
{
dfs1(g.to[i],now);
size[now]+=size[g.to[i]];
if(size[g.to[i]]>size[son[now]]) son[now]=g.to[i];
}
return ;
}//树剖第一遍预处理
void dfs2(int now,int F)
{
top[now]=F;
id[now]=++cnt;
Min[id[now]][0]=w[now];
if(!son[now]) return ;
dfs2(son[now],F);
for(int i=g.hd[now];i;i=g.nxt[i])
if(g.to[i]!=fa[now]&&g.to[i]!=son[now]) dfs2(g.to[i],g.to[i]);
return ;
}//树剖第二遍预处理
int query(int l,int r)
{
if(l>r) return 1e9;//这里这里，这句话一定要加！
//虽然我也不知道为什么QwQ
int k=lg[r-l+1];
return min(Min[l][k],Min[r-(1<<k)+1][k]);
}
int query_path(int x,int y)
{
if(!b.query(x,y)) return -1;//不连通直接-1
int res=1e9;
while(top[x]!=top[y])
{
if(depth[top[x]]<depth[top[y]]) swap(x,y);
res=min(res,query(id[top[x]],id[x]));
x=fa[top[x]];
}
if(depth[x]>depth[y]) swap(x,y);
res=min(res,query(id[x]+1,id[y]));
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++)
if(!b.query(a[i].u,a[i].v))
{
b.add(a[i].u,a[i].v);
g.add(a[i].u,a[i].v,a[i].w);
g.add(a[i].v,a[i].u,a[i].w);
}
//Kruskal 求出“最大瓶颈生成树”
for(int i=1;i<=n;i++)
if(!size[i]) dfs1(i,0);
//第一遍预处理
for(int i=1;i<=n;i++)
for(int j=g.hd[i];j;j=g.nxt[j])
if(depth[i]>depth[g.to[j]]) w[i]=g.dt[j];
else w[g.to[j]]=g.dt[j];
//把边权放到深度较大的点上
for(int i=1;i<=n;i++)
if(!id[i]) dfs2(i,i);
//第二遍预处理
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
//预处理出log
for(int k=1;(1<<k)<=n;k++)
for(int i=1;i+(1<<k)-1<=n;i++)
Min[i][k]=min(Min[i][k-1],Min[i+(1<<(k-1))][k-1]);
//ST 表
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
int u,v;
scanf("%d%d",&u,&v);
printf("%d
",query_path(u,v));
}
return 0;
}