当前位置：首页 > news >正文

Kruskal重构树

news 2025/7/16 7:19:14

Kruskal重构树 是 Kruskal 的扩展方法。
基于并查集（最小生成树）的思想，在合并分量的时候建立虚点作为新根，代表新连的这条边，即把原图的边权转换为新点的点权，形成一棵二叉树，这就具有很多良好性质了。
主要解决图上两点间最小边权最大值（最大边权最小值）问题。

建树

将原图的边按边权的一定顺序排序，保留原图的 $n$ 个结点；
遍历排序后的边 $u_i,v_i,w_,i)$ ，利用并查集判断当前边的两个端点 $u, v$ 是否连通，不连通则创建新节点 $p$ ，点权为 $w_i$ ，将 $u$ 和 $v$ 所在树的根节点作为 $p$ 的左右儿子，合并 $u, v$ 所在集合到 $p$ 中；

新树形态特点

$n - 1$ 条边 $2 n - 1$ 个点；（和最小生成树有所区别）
所有的叶子结点都为原图上的结点，无点权；
非叶子结点为新增的虚点，代表原图的一条边，点权为对应边的边权；

性质

堆性质：
- 从叶子到根的路径上，点权满足单调性；
路径查询：
- 两点间最小边权最大值 = $l c a (u, v)$ 的点权（大根堆）
- 证明：设 $p = l c a (u, v)$ ，则对于 $p$ 路径 $(u, v)$ 必须经过，由建图顺序， $p$ 是 $(u, v)$ 连通的最早边（在路径上权值最大）
子树性质：
- $x$ 的子树中所有点权 $≤wxmax\le w_{x_{max}}$ （大根堆）

例题

T1 星际导航

link
题意
给定 $n$ 个点 $m$ 条边的带权无向图，对于结点 $u, v$ ，从 $u$ 到 $v$ 路径上进过的边的边权最大值最小可能为多少。 $\le 10^5 , m \le 3 \times 10^5 ,q \le 10^5$

思路
看到“求两点间路径最大值的最小可能”可以想到 Kruskal重构树 。将原图上的边权从小到大排序建立大根堆，答案即为两点在新图上的 $l c a$ 所在点的点权。注意数组开大！！！

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,maxm=3e6+5;int idx,head[maxn];
struct EDGE{ int v,next; }e[maxm*2];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int fatr[maxn][23],dep[maxn];
void Dfs(int x,int fa){dep[x]=dep[fa]+1;for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa){fatr[v][0]=x;Dfs(v,x);}}
}int Get_lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=20;i>=0;i--)if(dep[fatr[x][i]]>=dep[y]) x=fatr[x][i];if(x==y) return x;for(int i=20;i>=0;i--)if(fatr[x][i]!=fatr[y][i]) x=fatr[x][i],y=fatr[y][i];return fatr[x][0];
}int fat[maxn];
int Find_fa(int x){ return (fat[x]==x?x:fat[x]=Find_fa(fat[x])); }int b[maxn*2];
struct LINE{ int x,y,z; }a[maxm];
int main(){int n,m; cin>>n>>m;for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].z;sort(a+1,a+m+1,[](LINE a,LINE b){ return a.z<b.z; });for(int i=1;i<=n*2;i++)fat[i]=i;int cnt=n;for(int i=1;i<=m;i++){int fx=Find_fa(a[i].x),fy=Find_fa(a[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;b[cnt]=a[i].z;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);}}for(int i=1;i<=cnt;i++)if(fat[i]==i) Dfs(i,0);int q; cin>>q;while(q--){int x,y; cin>>x>>y;if(Find_fa(x)!=Find_fa(y)) cout<<"impossible\n";else cout<<b[Get_lca(x,y)]<<"\n";}return 0;
}

T2 [NOI2018] 归程

link
题意
给定 $n$ 个点 $m$ 条边的带权无向图，对于边 $(u, v)$ 有 $(l, a)$ 表示这条边的长度和海拔。 $q$ 次询问从 $u$ 到 $1$ 路径上需要步行的最小值，其中对于每次询问海拔低于 $p$ 的边会被淹没，车从 $u$ 出发遇到淹没的边会停下，剩余路需要步行。每次询问强制在线。 $\le 2 \times 10^5,m \le 4 \times 10^5,q \le 4 \times 10^5$

思路
发现对于每次询问海拔 $≤p\le p$ 的边会淹没，考虑按海拔从高到低建一棵 Kruskal重构树 。则若子树 $x$ 中 $x$ 的海拔 $>p\gt p$ ，整棵子数中可以任意走。
设某个询问从 $v$ 出发，找到重构树上 $v$ 所在子树的根节点 $u$ ，答案就是求 $u$ 子树中结点到 $1$ 号点的最小值。
那么就先 $d ij s t r a$ 求出原图中所有点到 $1$ 点的最短路，建树后 $df s$ 整棵树， $d p$ 求出每棵子树中结点到 $1$ 点的最小值，可到达的就是从出发点 $u$ 开始向上倍增到最后一个海拔 $>p\gt p$ 的祖先。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=3e6+5;int idxr,headr[maxn];
struct EDGE{ int v,next; ll len; }er[maxn];
void Insertr(int u,int v,int len){er[++idxr]={v,headr[u],len};headr[u]=idxr;
}int idx,head[maxn];
EDGE e[maxn];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int fatr[maxn][23];
struct LINE{ int x,y,h; ll len; }b[maxn];
void Dfs(int x,int fa){for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa){fatr[v][0]=x;Dfs(v,x);b[x].len=min(b[x].len,b[v].len);}}
}ll Get_ans(int x,int nwh){for(int i=20;i>=0;i--)if(fatr[x][i]&&b[fatr[x][i]].h>nwh) x=fatr[x][i];return b[x].len;
}int fat[maxn];
int Find_fa(int x){ return (fat[x]==x?x:fat[x]=Find_fa(fat[x])); }int n;
ll dis[maxn];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
void Dij(){while(!q.empty()) q.pop();for(int i=1;i<=n;i++)dis[i]=1e18;dis[1]=0,q.push({dis[1],1});while(!q.empty()){int x=q.top().second,w=q.top().first;q.pop();for(int i=headr[x];i;i=er[i].next){int v=er[i].v;if(dis[v]>dis[x]+er[i].len){dis[v]=dis[x]+er[i].len;q.push({dis[v],v});}}}for(int i=1;i<=n;i++)b[i].len=dis[i];
}LINE a[maxn];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--){int m; cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].len>>a[i].h;Insertr(a[i].x,a[i].y,a[i].len),Insertr(a[i].y,a[i].x,a[i].len);}Dij();sort(a+1,a+m+1,[](LINE a,LINE b){ return a.h>b.h; });for(int i=1;i<=n*2;i++)fat[i]=i;int bc=0,cnt=n;for(int i=1;i<=m;i++){int fx=Find_fa(a[i].x),fy=Find_fa(a[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;b[cnt].len=1e18,b[cnt].h=a[i].h;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);bc++;if(bc==n-1) break;}}Dfs(cnt,0);int q,k,s; cin>>q>>k>>s;ll lstans=0;while(q--){int v0,p0; cin>>v0>>p0; int v=(v0+k*lstans-1)%n+1,p=(p0+k*lstans)%(s+1);lstans=Get_ans(v,p);cout<<lstans<<"\n";}idx=idxr=0;for(int i=1;i<=n*2;i++){headr[i]=head[i]=fat[i]=0,b[i]={0,0,0,0};	for(int j=0;j<=20;j++)fatr[i][j]=0;}}return 0;
}

T3 CF1706E Qpwoeirut and Vertices

link
题意
给出 $n$ 个点 $m$ 条边的不带权连通无向图， $q$ 次询问至少要加完编号前多少的边，才能使得 $[l, r]$ 中的所有点两两连通。 $\le n \le 10^5,m,q \le 2 \times 10^5$

思路
让一段点尽可能早的连通可以想到最小生成树，按原图边的顺序建一棵树，但是这样很难判断一段点是否连通。想到 Kruskal重构树 ，也类似建一棵树，发现求一段点连通最大需要用到的边相当于在新树上求这一段点的 $l c a$ 。
但是求一段点的 $l c a$ 复杂度显然不能接受，有一个经典方法是在新树上找到这一段点的最左边和最右边的两个结点，他们的 $l c a$ 就是新树上这段点的 $l c a$ 。
至于这两个点怎么求，就在新树上 $df s$ 序遍历，求这段点中最小和最大的 $df s$ 序，用线段树维护即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,maxm=2e5+5;int idx,head[maxn];
struct EDGE{ int v,next; }e[maxm*4];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int n,dfn[maxn],tim,fatr[maxn][23],dep[maxn],pl[maxn];
void Dfs(int x,int fa){if(x<=n) dfn[x]=++tim,pl[tim]=x;dep[x]=dep[fa]+1,fatr[x][0]=fa;for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa) Dfs(v,x);}
}struct TREE{ int mi,ma; }tree[maxn*4];
void Build(int rt,int l,int r){tree[rt].mi=1e9,tree[rt].ma=0;if(l==r){tree[rt].mi=tree[rt].ma=dfn[l];return;}int mid=(l+r)>>1;Build(rt*2,l,mid),Build(rt*2+1,mid+1,r);tree[rt].mi=min(tree[rt*2].mi,tree[rt*2+1].mi);tree[rt].ma=max(tree[rt*2].ma,tree[rt*2+1].ma);
}int Query_mi(int rt,int l,int r,int x,int y){if(x<=l&&r<=y) return tree[rt].mi;int mid=(l+r)>>1; int s=1e9;if(x<=mid) s=min(s,Query_mi(rt*2,l,mid,x,y));if(y>mid) s=min(s,Query_mi(rt*2+1,mid+1,r,x,y));return s;
}int Query_ma(int rt,int l,int r,int x,int y){if(x<=l&&r<=y) return tree[rt].ma;int mid=(l+r)>>1; int s=0;if(x<=mid) s=max(s,Query_ma(rt*2,l,mid,x,y));if(y>mid) s=max(s,Query_ma(rt*2+1,mid+1,r,x,y));return s;
}int Get_lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=20;i>=0;i--)if(dep[fatr[x][i]]>=dep[y]) x=fatr[x][i];if(x==y) return x;for(int i=20;i>=0;i--)if(fatr[x][i]!=fatr[y][i]) x=fatr[x][i],y=fatr[y][i];return fatr[x][0];
}int fat[maxn];
int Find_fa(int x){ return (fat[x]==x?x:fat[x]=Find_fa(fat[x])); }int b[maxn];
struct LINE{ int x,y,id; }a[maxm];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--){int m,q; cin>>n>>m>>q;for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y;a[i].id=i;}for(int i=1;i<=n*2;i++)fat[i]=i;int lnb=0,cnt=n;for(int i=1;i<=m;i++){int fx=Find_fa(a[i].x),fy=Find_fa(a[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;b[cnt]=i;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);lnb++;if(lnb==n-1) break;}}tim=0,Dfs(cnt,0);Build(1,1,n);while(q--){int x,y; cin>>x>>y;int ptl=Query_mi(1,1,n,x,y),ptr=Query_ma(1,1,n,x,y);cout<<b[Get_lca(pl[ptl],pl[ptr])]<<" ";}cout<<"\n";idx=0;for(int i=1;i<=cnt;i++) head[i]=dfn[i]=b[i]=0;}return 0;
}

T4 CF1416D Graph and Queries

link
题意
给定一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 个点的点权初始值为 $p_i$ ,所有 $p_i$ 互不相同。有 $q$ 次操作，分为两类：

1 v 查询与 $v$ 连通的点中， $p_u$ 最大的点 $u$ 并输出 $p_u$ ，然后让 $p_u = 0$ 。
2 i 将第 $i$ 条边删掉。

$\le n \le 2 \times 10^5,1 \le m \le 3 \times 10^5 ,1 \le q \le 5 \times 10^5$

思路
看到询问中有刪边操作，不好维护，考虑 时光倒流，将刪边改为加边。又看到点权会被修改，不好用普通并查集维护，考虑重构树。
按加边先后顺序建一棵重构树，对每个询问 $v$ ，倍增跳祖先确保所在子树中的边都没被删除，最后求子树中的最大值，由于还要将最大值设为 $0$ ，可以将重构树用 $df n$ 序线段树维护，重构树上的一棵子树相当于线段树上一段点，操作就变成线段树上区间查询单点修改了。
注意当最大值为 $0$ 时就没必要修改了。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxN=2e5+5,maxn=4e5+5,maxm=3e5+5,maxq=5e5+5;int idx,head[maxn];
struct EDGE{ int v,next; }e[maxm*4];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int n,fatr[maxn][23],tim,dfn[maxN],pl[maxN],st[maxn],ed[maxn];
void Dfs(int x,int fa){if(x<=n) dfn[x]=++tim,pl[tim]=x,st[x]=ed[x]=tim;fatr[x][0]=fa;for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa) Dfs(v,x);}
}void Dfs2(int x,int fa){if(!st[x]) st[x]=1e9;for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa){Dfs2(v,x);st[x]=min(st[x],st[v]);ed[x]=max(ed[x],ed[v]);}}
}int fat[maxn];
int Find_fa(int x){ return (fat[x]==x?x:fat[x]=Find_fa(fat[x])); }int a[maxN];
struct TREE{ int ma; }tree[maxN*4];
void Build(int rt,int l,int r){if(l==r){tree[rt].ma=a[pl[l]];return;}int mid=(l+r)>>1;Build(rt*2,l,mid),Build(rt*2+1,mid+1,r);tree[rt].ma=max(tree[rt*2].ma,tree[rt*2+1].ma);
}void Modify(int rt,int l,int r,int x,int y){if(l==r){tree[rt].ma=y;return;}int mid=(l+r)>>1;if(x<=mid) Modify(rt*2,l,mid,x,y);else Modify(rt*2+1,mid+1,r,x,y);tree[rt].ma=max(tree[rt*2].ma,tree[rt*2+1].ma);
}int Query(int rt,int l,int r,int x,int y){if(x<=l&&r<=y) return tree[rt].ma;int mid=(l+r)>>1; int s=0;if(x<=mid) s=max(s,Query(rt*2,l,mid,x,y));if(y>mid) s=max(s,Query(rt*2+1,mid+1,r,x,y));return s;
}int b[maxq],rl[maxN];
struct LINE{ int x,y,id; }ln[maxm];
struct QUE{ int op,x,id; }qt[maxq];
int main(){int m,q; scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++){scanf("%d",&a[i]);rl[a[i]]=i;}for(int i=1;i<=m;i++)scanf("%d%d",&ln[i].x,&ln[i].y);for(int i=1;i<=q;i++)scanf("%d%d",&qt[i].op,&qt[i].x);int cut=0;for(int i=q;i>=1;i--){if(qt[i].op==2) cut++,ln[qt[i].x].id=cut,b[cut]=qt[i].x;qt[i].id=cut;}sort(ln+1,ln+m+1,[](LINE a,LINE b){ return a.id<b.id; });for(int i=1;i<=n*2;i++)fat[i]=i;int lnb=0,cnt=n;for(int i=1;i<=m;i++){int fx=Find_fa(ln[i].x),fy=Find_fa(ln[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;b[cnt]=i;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);lnb++;if(lnb==n-1) break;}}for(int i=1;i<=cnt;i++)if(fat[i]==i) Dfs(i,0);for(int i=n;i<=cnt;i++)if(fat[i]==i) Dfs2(i,0);Build(1,1,n);int gs=0;for(int i=1,tmp=0,ans=0;i<=q;i++)if(qt[i].op==1){tmp=qt[i].x;for(int j=20;j>=0;j--)if(fatr[tmp][j]&&ln[b[fatr[tmp][j]]].id<=qt[i].id) tmp=fatr[tmp][j];if(gs<n) ans=Query(1,1,n,st[tmp],ed[tmp]);else ans=0;printf("%d\n",ans);if(ans) Modify(1,1,n,dfn[rl[ans]],0),gs++;}return 0;
}

T5 [AGC002D] Stamp Rally

link
题意
一张无向连通图， $q$ 次询问从两个点 $x$ 和 $y$ 出发，希望经过的点数量等于 $z$ （每个点可以重复经过，但是重复经过只计算一次），求经过的边最大编号最小是多少。 $\le n \le 10^5, n-1 \le m \le 10^5 , 1 \le q \le 10^5$

思路
求边编号的最小值想到重构树，按原图边的顺序建一棵重构树，记录树上每棵子树中真点的数量。对于询问 $(x, y)$ ，从 $x, y$ 贪心向上跳祖先不好维护。考虑二分答案，只跳权值小于二分值的祖先，然后判断可经过点数的合法性。复杂度 $(n l o g n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5,maxm=1e5+5;int idx,head[maxn];
struct EDGE{ int v,next; }e[maxm*4];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int n,fatr[maxn][23],dep[maxn],siz[maxn];
void Dfs(int x,int fa){if(x<=n) siz[x]=1;dep[x]=dep[fa]+1,fatr[x][0]=fa;for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa){Dfs(v,x);siz[x]+=siz[v];}}
}int Get_lca(int x,int y){if(dep[x]<dep[y]) swap(x,y);for(int i=20;i>=0;i--)if(dep[fatr[x][i]]>=dep[y]) x=fatr[x][i];if(x==y) return x;for(int i=20;i>=0;i--)if(fatr[x][i]!=fatr[y][i]) x=fatr[x][i],y=fatr[y][i];return fatr[x][0];
}int fat[maxn];
int Find_fa(int x){ return (fat[x]==x?x:fat[x]=Find_fa(fat[x])); }int b[maxn];
bool Check(int d,int x,int y,int z,int lca){for(int i=20;i>=0;i--){if(fatr[x][i]&&b[fatr[x][i]]<=d) x=fatr[x][i];if(fatr[y][i]&&b[fatr[y][i]]<=d) y=fatr[y][i];}if(dep[x]>dep[lca]&&dep[y]>dep[lca]) return (siz[x]+siz[y]>=z);return (siz[x]>=z);
}struct LINE{ int x,y,id; }a[maxm];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int m; cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y;a[i].id=i;}for(int i=1;i<=n*2;i++)fat[i]=i;int lnb=0,cnt=n;for(int i=1;i<=m;i++){int fx=Find_fa(a[i].x),fy=Find_fa(a[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;b[cnt]=i;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);lnb++;if(lnb==n-1) break;}}Dfs(cnt,0);int q; cin>>q;while(q--){int x,y,z; cin>>x>>y>>z;int lca=Get_lca(x,y);int l=0,r=m,mid;while(l+1<r){mid=(l+r)>>1;if(Check(mid,x,y,z,lca)) r=mid;else l=mid;}cout<<r<<"\n";}return 0;
}

T6「yyOI R1」youyou 的军训

link
题意
较长懒得写了……

思路
模拟样例发现这是一个连通性问题，边权带修改，普通并查集不好维护，考虑重构树，按边权从大到小建树。和前面几题差不多，注意 操作3 有一点细节。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=8e5+5;int idx,head[maxn];
struct EDGE{ int v,next; }e[maxn*2];
void Insert(int u,int v){e[++idx]={v,head[u]};head[u]=idx;
}int fatr[maxn][23];
void Dfs(int x,int fa){fatr[x][0]=fa;for(int i=0;i<20;i++)fatr[x][i+1]=fatr[fatr[x][i]][i];for(int i=head[x];i;i=e[i].next){int v=e[i].v;if(v!=fa) Dfs(v,x);}
}int fat[maxn];
int Find_fa(int x){return (fat[x]==x?x:fat[x]=Find_fa(fat[x]));
}int siz[maxn],id[maxn],b[maxn];
struct LINE{ int x,y,z,d; }a[maxn];
vector<pair<int,int> >md;
int main(){int n,m,q; cin>>n>>m>>q;for(int i=1;i<=m;i++){cin>>a[i].x>>a[i].y>>a[i].z;a[i].d=i;}sort(a+1,a+m+1,[](LINE a,LINE b){ return a.z>b.z; });for(int i=1;i<=n*2;i++){fat[i]=i;if(i<=n) siz[i]=1;}int cnt=n,lns=0;for(int i=1;i<=m;i++){int fx=Find_fa(a[i].x),fy=Find_fa(a[i].y);if(fx!=fy){fat[fx]=fat[fy]=++cnt;siz[cnt]=siz[fx]+siz[fy],b[cnt]=a[i].z,id[a[i].d]=cnt;Insert(fx,cnt),Insert(cnt,fx);Insert(fy,cnt),Insert(cnt,fy);lns++;if(lns==n-1) break;}}for(int i=1;i<=cnt;i++)if(fat[i]==i) Dfs(i,0);int lst=0;while(q--){int op; cin>>op;if(op==1){int x; cin>>x;lst=x;for(int i=0;i<md.size();i++)b[id[md[i].first]]=md[i].second;md.clear();}else if(op==2){int x; cin>>x;for(int i=20;i>=0;i--)if(fatr[x][i]&&b[fatr[x][i]]>=lst) x=fatr[x][i];cout<<siz[x]<<"\n";}else{int x,y; cin>>x>>y;md.push_back({x,y});}}return 0;
}