最基本的用途就是维护连通图中路径权值的最值问题
相关题目:$【BZOJ3732】Network$

-主要思想

本来对于一个连通图中的路径最值,我们采用的是建立最小生成树,
然后对两点在最小生成树中的路径暴力求最值或者用树剖加线段树的方法

但是这样要么慢,要么实现起来比较麻烦
这时候可以用到一种叫Kruskal重构树的算法

实现方式是在Kruskal连边时不直接连边,而是新建一个点权为该边边权的结点
将这条边的两个端点的整颗子树连到该节点上作为儿子,
各个子树的根用并查集维护一下就可以了

这样建出来的树具有一些性质:
1. 是一个大根堆(因为Kruskal连边时边权由小到大)
2. 原树和新树两点间路径上的边权/点权最大值相等
然后把性质1,2综合起来我们可以得到:原树上两点间边权最大值等于新树上两点的lca的点权

利用这个性质就可以很方便的求路径最值

下面是示意图

1
1

注意在新树中的圆点中的数字表示原树中的点的编号,它们是没有点权的
而方点代表的就是新建的点,其中的数字表示的是其点权

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
const int N=31000;
using namespace std;
struct node{int u,v,w;}e[N];
int cmp(const node &x,const node &y){return x.w<y.w;}
int n,m,k,fa[N],to[N<<1],nxt[N<<1],head[N],cnt,val[N],tot;
int size[N],son[N],dep[N],top[N];
inline void add(int u,int v){
to[++cnt]=v,nxt[cnt]=head[u];
head[u]=cnt;
}
int getf(int x){return fa[x]==x?x:fa[x]=getf(fa[x]);}
void dfs1(int u,int ff){
size[u]=1;
dep[u]=dep[ff]+1;
fa[u]=ff;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(v==ff) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topp){
top[u]=topp;
if(son[u]) dfs2(son[u],topp);
for(int i=head[u];i;i=nxt[i])
if(to[i]!=fa[u]&&to[i]!=son[u]) dfs2(to[i],to[i]);
}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
int main(int argc, char const *argv[]) {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
for(int i=1;i<=2*n-1;i++) fa[i]=i;
tot=n;
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++){
int fx=getf(e[i].u),fy=getf(e[i].v);
if(fx==fy) continue;
val[++tot]=e[i].w;
add(tot,fx),add(tot,fy);
fa[fx]=fa[fy]=tot;
}
dfs1(tot,0),dfs2(tot,tot);
int x,y;
while(k--){
scanf("%d%d",&x,&y);
printf("%d\n",val[lca(x,y)]);
}
return 0;
}