本文共 761 字，大约阅读时间需要 2 分钟。

正题

题目链接:

题目大意

一张图，每次询问两个点，求这两个点之间路径的最大值的最小是多少。

解题思路

构造一颗$Kruskal$重构树然后就是模板了。

$code$

#include
   
    #include
    
     #include
     
      using namespace std;const int N=2e5+10;struct node{
   	int x,y,w; }e[N];struct edge_node{
   	int to,next;}a[N];int n,m,k,tot,cnt,root,ls[N],val[N];int top[N],dep[N],siz[N],son[N],fa[N];void addl(int x,int y){
   	a[++tot].to=y;	a[tot].next=ls[x];	ls[x]=tot;}bool cmp(node x,node y){
   return x.w
      
       siz[son[x]])			son[x]=y;	}}void dfs2(int x){
   	if(son[x]){
   		top[son[x]]=top[x];		dfs2(son[x]);	}	for(int i=ls[x];i;i=a[i].next){
   		int y=a[i].to;		if(y==fa[x]||y==son[x]) continue;		top[y]=y;dfs2(y);	}}int LCA(int x,int y){
   	while(top[x]!=top[y]){
   		if(dep[top[x]]
      
     
    
   

转载地址：http://tuwaf.baihongyu.com/