链接
就这个题，调了三天。
在累的老眼昏花的时候发现了一些有趣的事情：
（此时内心：qwq?qwq!qwq...qwq!QAQAQAQ）
--------------------------------------------------------闲扯完毕，手动分割-------------------------------------------------------
简化一下问题
就是给一张图（先假设这张图连通），设两个点u,v，u,v之间的一条路径是L，L上最短的边是minL,要使minL最大。
然后开始思索。。。
发现有很多边是没用的，砍完了就成了树了。此时恢复任意一条边去替换图内的边，肯定会使答案更劣。
这就是一个最大生成树了。
对于每个询问（u,v），就是求T图中u到v的路径上的最大值，这个就用树上倍增维护了吧。
如果这张图本来就不连通呢？
在并查集的操作里，就可以判有没有解了。只需要在dfs的时候注意把所有点都考虑到就好了（类似tarjan里的那个循环）。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define maxn 100005
#define maxm 500005
using namespace std;
int n,m,q;
int f[maxn][15],w[maxn][15],dep[maxn],fa[maxn];
int x,y,z;
struct node{int y,nxt,len;
}e[maxn*2];//最大生成树的图
struct path{int x,y,z;
}p[maxm];//生成树存边
int head[maxn],tot=0;inline bool cmp(path a,path b){return a.z>b.z;
}inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);
}//Kruskalinline void ad(int x,int y,int z){++tot;e[tot].y=y;e[tot].nxt=head[x];e[tot].len=z;head[x]=tot;
}
inline void dfs(int u){for(int i=head[u];i;i=e[i].nxt){int y=e[i].y;if(dep[y]==0){dep[y]=dep[u]+1;f[y][0]=u;w[y][0]=e[i].len;dfs(y);}}
}
inline void pre()//prepare
{for(int i=1;i<=n;i++){if(dep[i]==0){dep[i]=1;f[i][0]=0;dfs(i);}}for(int i=1;i<=14;i++)for(int x=1;x<=n;x++)f[x][i]=f[f[x][i-1]][i-1],w[x][i]=min(w[x][i-1],w[f[x][i-1]][i-1]);
}
inline int lca(int a,int b){if(dep[a]<dep[b])swap(a,b);int ans=1000000000;for(int i=14;i>=0;i--)if(dep[f[a][i]]>=dep[b])ans=min(ans,w[a][i]),a=f[a][i];//一定要先更新再修改 if(a==b)return ans;for(int i=14;i>=0;i--)if(f[a][i]!=f[b][i])ans=min(ans,min(w[a][i],w[b][i])),a=f[a][i],b=f[b][i];ans=min(ans,min(w[a][0],w[b][0]));return ans;
}
int main()
{memset(w,0x3f,sizeof(w));scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);for(int i=1;i<=n;i++)fa[i]=i;sort(p+1,p+m+1,cmp);int x,y,z,cnt=0;for(int i=1;i<=m;i++){x=p[i].x;y=p[i].y;z=p[i].z;int fx=find(x),fy=find(y);if(fx!=fy){fa[fx]=fy;ad(x,y,z);ad(y,x,z);++cnt;if(cnt==n-1)break;}}pre();scanf("%d",&q);int a,b;for(int i=1;i<=q;i++){scanf("%d%d",&a,&b);if(find(a)!=find(b))printf("-1\n");else printf("%d\n",lca(a,b));}
}完结撒花~