Kruskal 重构树学习笔记

## 说在前面 本人仅对此算法给予更完整的补充，如有错误，请轻喷。 ## 定义 顾名思义，$\text{Kruskal}$ 重构树就是基于 $\text{Kruskal}$ 的最小生成树算法在无向图中得出的树所构造而成的树。 可以根据它的构造方法来进一步完善它的定义。 ## 构造 - 把最小生成树上的边从小到大取出来。 这一步在实现上相当于边做 $\text{Kruskal}$ 边构造重构树。 - 设这条边的为 $x$ 与 $y$ 连边，那么我们新建节点 $now$，将 $now$ 连向 $x,y$，将 $now$ 的点权设为这条边的边权，$x$ 与 $y$ 之间不连边。注意这里向 $x$ 连边实际上指的是向 $x$ 所在子树的根节点连边。 - 建完最小生成树之后，重构树也就建好了。 举个例子。  这是一张无向带权图。  这是这张图的最小生成树。 我们将每条边从小到大建立 $\text{Kruskal}$ 重构树。 注：新点括号中的是点权。     这样我们就建好了这个图的 $\text{Kruskal}$ 重构树。 **code** ```cpp void Ex_Kruskal() { int cnt=n; sort(e+1,e+m+1,cmp); for (int i=1;i<2*n;++i) f[i]=i; for (int i=1;i<=m;++i) { int u=get(e[i].x),v=get(e[i].y); if (u!=v) { ++cnt; f[u]=f[v]=cnt; val[cnt]=e[i].z; add(cnt,u);add(cnt,v); if (cnt==2*n-1) break; } } } ``` ## 性质 - 是一棵二叉树。 - 如果是按最小生成树建立的话是一个大根堆。 - **强大性质**：原图中两个点间所有路径上的边最大权值的最小值 $=$ 最小生成树上两点简单路径的边最大权值 $=$ $\text{Kruskal}$ 重构树上两点 $\text{LCA}$ 的点权。 利用这个性质，我们可以找到到点 $x$ 的简单路径上的边最大权值的最小值 $\le val$ 的所有点 $y$。可以发现都在 $\text{Kruskal}$ 重构树上的某一棵子树内，且恰好为该子树的所有叶节点。 **具体细节** 我们在 Kruskal 重构树上找到 $x$ 到根的路径上权值 $\le val$ 的最浅的节点,这就是那棵子树的根节点。 - 如果题目要求最小权值最大值，可以建最大生成树的重构树从而达到一样的效果。 ## 例题1 $\text{BZOJ3732}$ 网络。 **Description** 给定无向图，多次询问从 $A$ 点走到 $B$ 点的所有路径中，最长的边最小值是多少？ **solution** 题目已经很明显了，建立 $\text{Kruskal}$ 重构树，那么答案就是 $A$ 点与 $B$ 点 $\text{LCA}$ 的点权。 ## 例题2 **Description** 给定带权树，定义 $d(x,y)$ 为 $x,y$ 这两个点之间路径上的最小值，定义一个点 $x$ 的权值为 $\sum\limits_{i=1}^nd(x,i)$，输出树上点的最大权值。 **solution** 回忆建立 $\text{Kruskal}$ 重构树的建立过程，每个新点实际上都代表这一条边，且它是这棵子树上边权的极值。那我们就可以枚举每一个新点，这条边能产生贡献的就是它的左子树连向右子树的路径或右子树连向左子树的路径。 建立 $dfn$ 序，对于每个点就是区间加的操作即可。 ## 例题3 经典例题。 $\text{BZOJ}3551\ Peaks$ 加强版。 **Description** 给定无向图，每个点有一个点权 $h_i$，每条路径有一个权值 $w_i$，每次询问从点 $x$ 开始只经过边权 $\le val$ 的路径所能到达的点中点权第 $k$ 大的点，无解输出 $-1$。 **solution** 利用在上文性质中讲的做法，每次找到点 $x$ 在 $\text{Kruskal}$ 重构树上的祖先深度最浅且点权 $\le val$ 的点，那么答案就是这棵字数中的叶子结点的点权第 $k$ 大。 我们发现这棵树是静态的，可以按照 $dfn$ 序，直接利用主席树区间求第 $k$ 大即可。 **如果想交题的话可以来例题4（其实就是例题1）** [loj 最小瓶颈路 加强版](https://loj.ac/p/137) ## 不过瘾？来点刺激的 [[AGC002D] Stamp Rally](https://www.luogu.com.cn/problem/AT1998) **solution** 考虑二分答案，那么就给了点在 $\text{Kruskal}$ 重构树上的限制，也就是一个点可以找到深度最浅的一个祖先，满足它的点权小于二分值，那么这个点就可以走到这棵子树上的所有点。 记录每棵子数的叶子结点个数，然后 $x,y$ 倍增计算答案，然后与 $z$ 比较即可完成二分。 在细节上，需要注意在倍增的时候，要记得判断 $x,y$ 最后跳到的是不是一个点，小心算重。 关于题目模型，一个无向连通图，求两点路径最大权值最小值较为容易想到 $\text{Kruskal}$ 重构树，且这题限制了经过点的个数要恰好为 $z$，不能大也不能小，所以二分是一个比较好的解决方案。 代码复杂度较低，时间复杂度为两个 $\log$。 **code** ```cpp #include<cstdio> using namespace std; int n,m,fa[200010],tot,x,y,val[200010],f[200010][18],cnt,dep[200010],ans,leave[200010],q,z; struct node{int last,en,next;} e[400010]; int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} void add(int x,int y) { e[++tot].en=y; e[tot].next=e[x].last; e[x].last=tot; } void dg(int x,int fa) { f[x][0]=fa;dep[x]=dep[fa]+1; for (int i=e[x].last;i;i=e[i].next) if (e[i].en!=fa) dg(e[i].en,x),leave[x]+=leave[e[i].en]; } int check(int x,int y,int mid) { for (int i=17;i>=0;i--) { if (val[f[x][i]]<=mid) x=f[x][i]; if (val[f[y][i]]<=mid) y=f[y][i]; } if (x==y) return leave[x]; else return leave[x]+leave[y]; } int main() { scanf("%d%d",&n,&m); cnt=n; for (int i=1;i<2*n;i++) fa[i]=i; for (int i=1;i<=n;i++) leave[i]=1; val[0]=0x3f3f3f3f; for (int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if (cnt==2*n-1) continue; int u=get(x),v=get(y); if (u!=v) { ++cnt; fa[u]=fa[v]=cnt; val[cnt]=i; add(cnt,u);add(cnt,v); } } dg(cnt,0); for (int j=1;j<=17;j++) for (int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d",&q); for (int i=1;i<=q;i++) { scanf("%d%d%d",&x,&y,&z); int l=1,r=m,mid;ans=0; while (l<=r) { mid=(l+r)>>1; if (check(x,y,mid)>=z) ans=mid,r=mid-1; else l=mid+1; } printf("%d\n",ans); } return 0; } ``` [[NOI2018] 归程](https://www.luogu.com.cn/problem/P4768) **solution** 经典套路。 建立最大生成树的 $\text{Kruskal}$ 重构树，那么对于水位线的限制就解决了。具体操作就是利用重构树的性质，一定能在起点的祖先中找到一个深度最浅且权值 $>=p$ 的点，这个点的子树里的叶子结点就是能开车直接走到的点，剩下的步行即可。所以直接取所有叶子结点中距离 $1$ 最近的即可。 一开始算出所有点与 $1$ 的最短路即可。 但是这道题的最有意思的地方就是这个求最短路。 笔者刚开始写这道题的时候因不知原因 $\text{RE}$ 了好多次，发现自己的 $\text{SPFA}$ 跑得很慢，后来才想起这道题是归程…… 出题人随手卡了一手 $\text{SPFA}$，所以记得写 $\text{Dijkstra}$。 ~~不要尝试在 NOI 出题人面前班门弄斧，除非你很强（~~ **code** ```cpp #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int n,m,x,y,z,w,cnt,d[1000010],tot,tot1,fa[1000010],val[1000010],f[1000010][19]; int leave[1000010]; int v,p,Q,K,s,ans,T; bool bz[1000010]; struct node1{int x,y,z;} a[1000010]; struct node{int last,en,next;} e[2000010]; struct edge{int last,en,next,v;} g[2000010]; void add(int x,int y) { e[++tot].en=y; e[tot].next=e[x].last; e[x].last=tot; } void add(int x,int y,int z) { g[++tot1].en=y; g[tot1].v=z; g[tot1].next=g[x].last; g[x].last=tot1; } bool cmp(node1 x,node1 y){return x.z>y.z;} void dijkstra() { priority_queue<pair<int,int> >q; memset(d,63,sizeof(d)); memset(bz,0,sizeof(bz)); d[1]=0; q.push(make_pair(0,1)); while (q.size()) { int x=q.top().second;q.pop(); if (bz[x]) continue; bz[x]=true; for (int i=g[x].last;i;i=g[i].next) { int y=g[i].en; if (d[y]>d[x]+g[i].v) { d[y]=d[x]+g[i].v; q.push(make_pair(-d[y],y)); } } } } int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} void dg(int x,int fa) { bool bj=false; f[x][0]=fa; for (int i=e[x].last;i;i=e[i].next) if (e[i].en!=fa) dg(e[i].en,x),leave[x]=min(leave[x],leave[e[i].en]),bj=true; if (!bj) leave[x]=d[x]; } int find(int x,int p) { for (int i=18;i>=0;i--) if (val[f[x][i]]>p) x=f[x][i]; return x; } int main() { scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); tot=0;tot1=0; for (int i=1;i<=2*n;i++) e[i].last=g[i].last=0; for (int i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&z,&w); add(x,y,z);add(y,x,z); a[i].x=x;a[i].y=y;a[i].z=w; } sort(a+1,a+m+1,cmp); cnt=n; for (int i=1;i<=2*n;i++) fa[i]=i; for (int i=1;i<=m;i++) { int u=get(a[i].x),v=get(a[i].y); if (u!=v) { cnt++; fa[u]=fa[v]=cnt;val[cnt]=a[i].z; add(cnt,u);add(cnt,v); if (cnt==2*n-1) break; } } dijkstra(); memset(leave,63,sizeof(leave)); dg(cnt,0); for (int j=1;j<=18;j++) for (int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d%d%d",&Q,&K,&s); ans=0; for (int i=1;i<=Q;i++) { scanf("%d%d",&v,&p); v=(v+K*ans-1)%n+1;p=(p+K*ans)%(s+1); int pos=find(v,p); printf("%d\n",ans=leave[pos]); } } return 0; } ``` ## 还不够？来看这道吧 [[CERC2016]机棚障碍 Hangar Hurdles](https://www.luogu.com.cn/problem/P3684) **solution** 如果我们求出了每个点能容纳的最大集装箱大小 $d$，那么实际上本题要求的就是所有起点到终点的路径上边的权值最小值的最大值。 容易想到 $\text{Kruskal}$ 重构树，将每个点与四周连边，然后建树，跑倍增求 $\text{LCA}$ 点权即可。 $d$ 可以二分加二维前缀和求，可以在 $O(n^2\log n)$ 完成。 但是我们发现每个点都连边实在太多了，存不下。考虑观察性质，我们发现，如果在 $d$ 相同的点之间移动，是不会对最终答案造成影响的，所以我们完全可以把相邻的 $d$ 相同的点合并起来，再连边，这样边数就少的多。合并的过程可以采用 $\text{BFS}$ 在 $O(n^2)$ 内完成。关于去重，可以使用 $\text{unordered\_map}$，可以认为它是常数级别的。 在实现细节方面，我们注意到，由于障碍的存在，所以可能最后得到的是森林而不是一棵树。考虑到树与树之间是不连通的，所以我们完全可以新建一个节点连向这些树，并把点权设为 $0$，就可以直接按照普通一棵树的情况来做了。 在实现的时候，分步调试，也就是每写一个架构就测试一下这个架构是不是对的，这样可以让最后调试的时候轻松很多。个人写完加调完只用了 1 个小时左右，一遍过，总之不是很难写，但是码量确实有点长，相信各位可以有耐心完成这道题，是一道不错的思维难度适中的，练习码力的题目。 **code** ```cpp #include<cstdio> #include<algorithm> #include<unordered_map> #include<queue> using namespace std; struct Hash { size_t operator()(pair<int,int> a)const { return ((long long)a.first<<32)|a.second; } }; unordered_map<pair<int,int>,bool,Hash> ma; struct node1{int x,y,z;} g[2000010]; int n,a[1010][1010],d[1010][1010],cnt,id[1010][1010]; int val[2000010],fa[2000010],f[2000010][21]; int fx[5][3],tot1,tot; struct node{int last,en,next;} e[10000010]; char ch[1010][1010]; bool bz[1010][1010],ru[2000010]; int dep[2000010]; int q,x1,y1,x2,y2; bool check(int d,int x,int y) { int x1=x-d,y1=y-d,x2=x+d,y2=y+d; if (x1<=0||y1<=0||x2>n||y2>n) return false; if (a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1]>0) return false; return true; } void bfs(int s,int t) { queue<pair<int,int> > q; bz[s][t]=true; q.push(make_pair(s,t)); id[s][t]=++cnt; while (!q.empty()) { int x=q.front().first,y=q.front().second;q.pop(); for (int k=1;k<=4;k++) { int xx=fx[k][1]+x,yy=fx[k][2]+y; if (xx>0&&xx<=n&&yy>0&&yy<=n&&ch[xx][yy]=='.'&&!bz[xx][yy]&&d[xx][yy]==d[x][y]) { bz[xx][yy]=true; q.push(make_pair(xx,yy)); id[xx][yy]=cnt; } } } } void insert(int x,int y,int z) { g[++tot1].x=x;g[tot1].y=y;g[tot1].z=z; } bool cmp(node1 x,node1 y){return x.z>y.z;} int get(int x){return fa[x]==x?x:fa[x]=get(fa[x]);} void add(int x,int y) { e[++tot].en=y; e[tot].next=e[x].last; e[x].last=tot; } void dfs(int x,int fa) { dep[x]=dep[fa]+1;f[x][0]=fa; for (int i=e[x].last;i;i=e[i].next) if (e[i].en!=fa) dfs(e[i].en,x); } int lca(int x,int y) { if (dep[x]<dep[y]) swap(x,y); for (int i=20;i>=0;i--) if (dep[f[x][i]]>=dep[y]) x=f[x][i]; if (x==y) return x; for (int i=20;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int main() { fx[1][1]=fx[3][2]=-1;fx[2][1]=fx[4][2]=1; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%s",ch[i]+1); for (int j=1;j<=n;j++) a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(ch[i][j]=='#'); } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (ch[i][j]=='.') { int l=0,r=n/2,mid,ret=0; while (l<=r) { mid=(l+r)>>1; if (check(mid,i,j)) l=mid+1,ret=mid; else r=mid-1; } d[i][j]=ret*2+1; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (ch[i][j]=='.'&&!bz[i][j]) bfs(i,j); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (ch[i][j]=='.') { for (int k=1;k<=4;k++) { int xx=fx[k][1]+i,yy=fx[k][2]+j; if (xx>0&&xx<=n&&yy>0&&yy<=n&&ch[xx][yy]=='.'&&id[xx][yy]!=id[i][j]&&!ma[make_pair(id[xx][yy],id[i][j])]) { ma[make_pair(id[xx][yy],id[i][j])]=true; ma[make_pair(id[i][j],id[xx][yy])]=true; insert(id[i][j],id[xx][yy],min(d[i][j],d[xx][yy])); insert(id[xx][yy],id[i][j],min(d[i][j],d[xx][yy])); } } } sort(g+1,g+tot1+1,cmp); for (int i=1;i<=2*cnt;i++) fa[i]=i; for (int i=1;i<=tot1;i++) { int u=get(g[i].x),v=get(g[i].y); if (u!=v) { ++cnt;ru[u]=true;ru[v]=true; fa[u]=fa[v]=cnt;val[cnt]=g[i].z; add(cnt,u);add(cnt,v); } } int bj=0; for (int i=1;i<=cnt;i++) if (!ru[i]) bj++; if (bj>1) { for (int i=1;i<=cnt;i++) if (!ru[i]) add(cnt+1,i); val[++cnt]=0; } dfs(cnt,0); for (int j=1;j<=20;j++) for (int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; scanf("%d",&q); for (int i=1;i<=q;i++) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); if (id[x1][y1]==id[x2][y2]) printf("%d\n",d[x1][y1]); else printf("%d\n",val[lca(id[x1][y1],id[x2][y2])]); } return 0; } ``` ## 其他习题 原谅作者做题量不是很大，不是很能找到了，如果你有习题，可以在评论区留言。 感谢评论区各位大佬的贡献，下面是题目整理，大家可以选择性的做。 [P1967 [NOIP2013 提高组] 货车运输](https://www.luogu.com.cn/problem/P1967) [P4899 [IOI2018] werewolf 狼人（上下界重构树）](https://www.luogu.com.cn/problem/P4899) [[ARC098F] Donation（重构树上 dp）](https://www.luogu.com.cn/problem/AT_arc098_d) [[CF1578L] Labyrinth](https://www.luogu.com.cn/problem/CF1578L) [P4197 Peaks ](https://www.luogu.com.cn/problem/P4197) [[CF1706E] Qpwoeirut and Vertices](https://www.luogu.com.cn/problem/CF1706E) [[CF1628E] Groceries in Meteor Town](https://www.luogu.com.cn/problem/CF1628E) ## 参考文献 [网上博客](https://blog.csdn.net/hwzzyr/article/details/81190442) [OI-wiki](https://oi-wiki.org/graph/mst/)