题解 P4716 【【模板】最小树形图】
yybakioi
2019-12-02 13:55:12
## 写在前面的话
1. 作者水平不够，如果看不懂，差不多就是我错了
1. 本文**主要**是补充$tarjan$优化朱刘算法这个黑科技，因为大多数人都说只要暴力朱刘就够了，如果不把这个东西介绍出来，它永远也不会成为考点
1. 本文会顺便**简单**介绍朱刘，因为网上的证明比较少，它也是tarjan优化的前提，另外感觉其他题解一上来就是一堆生僻的名词，很劝退
1. 我想我已经开始逐级改变了我写题解的目的了，不再是为了自己的复习或者巩固，学的再好也会忘记,只落得悲伤与痛苦了，而是为了能够真正介绍知识给大家了，一个人的意志很薄弱，而人民的力量是无限的。
1. 作者不可能介绍到所有前置知识，部分还得自行根据需要查询相关资料,因此需要有一定基础的人阅读本文
1. 一切都将逝去，唯有修涵永生。
## 契约
1. $(N^i)$表示注释$i$
1. $in[x]$表示$x$的入边的最小边权;
1. $pre[x]$表示$x$的入边，边权为$in[x]$的另外一端。
1. $d[x]$表示左偏树中$x$的距离
1. $a[x]$表示左偏树中$x$的点权
1. $l[x]$表示二叉树中，$x$的左儿子，同样的道理可以定义$r[x]$
1. $dep[x]$表示有根树中$x$的深度，$dep[\text{根}]$是$0$还是$1$无所谓
1. $sz[x]$表示有根树中以$x$为根的子树大小
1. 图论的时间复杂度分析中，默认$n$表示点数，$m$表示边数
1. 部分二元组$(u,v)$默认表示$u$连向$v$的一条边
1. 部分三元组$(u,v,w)$默认表示表示$u$连向$v$的边权为$w$的边
1. 接下来所有的套路都是在无重边的基础之上，因为重边你可以特判掉，选最小的那条即可。
## 朱刘算法
1. 考虑树形图的性质，每个点都有唯一的入边（根节点除外，以后讨论入边，都不考虑根节点），于是我们提出这样一个算法，强制选择每个点边权最小的入边，这样如果不存在环，我们**肯定**得到了最小的树形图。
1. 考虑如何处理环，有一条性质，因为这个环是由最小的入边所形成的环，因此**存在**一棵最小树形图，只缺少了环上的一条边，而且缺少的这条边所指向的点的入边必在**该棵**最小树形图上$(N^1)$。
1. 我们想要这个环缩成一个点$cnt$，而且要表现环上的每条边选与不选，对于进入环上的每条边$(u,v,w)$,$v$为环上的点,$u$非环上的点，令$w-=in[v]$，然后$v=cnt$，答案强制选上环上的边权，然后删除环上所有的内部连边$(N^2)$,把这个环缩成一个点，递归进行。
1. 每次形成一个环会至少少一个点，时间复杂度$O(nm)$。
---
$(N_1)$:
可以这样考虑证明，假设存在一棵最小树形图$T$,从$T$出发，肯定可以走到环上的某个点，假设走到了$x_0$，此时$x_0$已经有入边了，假设环长$L$,从$x_0$开始，顺时针给环上的点标号$x_0,x_1,x_2,...,x_{L-1}$,此时我们考虑$x_1$,对于$pre[x_1]$,我们可以删掉最小树形图上的$(pre[x_1],x_1)$，连上$(x_0,x_1)$,这样肯定不会变劣答案,可以证明的是，这样得到的还是一棵最小树形图,意味着环上$(x_0,x_1)$的边权等于$in[x_1]$,然后用同样的方法考虑$(x_1,x_2)$,依次类推，我们发现我们环上唯一不能选的边只有$(x_{L-1},x_0)$。
$(N_2)$:
这是一个常见贪心技巧，不知道的人应该仔细理解，自己给出证明。
## 左偏树
### 外节点
定义：二叉树中，一个节点没有左儿子或者右儿子就叫做外节点，或者理解为儿子个数小于等于1。
### 左偏树的距离
定义：在左偏树中，一个节点$x$的子树中，找到深度最大的外节点$y$，那么$dep[y]-dep[x]$就叫做左偏树中$x$到$y$的距离，以后谈距离省略左偏树，特别地空节点距离为$-1$。
### 左偏树
定义：如果一棵二叉树满足以下性质
1. 二叉堆（以后默认为小根堆进行讨论）
1. 对于任意一个节点$x$，有$d[l[x]]\geq d[r[x]]$
我们就把这个二叉树叫做左偏树。
### 左偏树的性质
1. $d[x]=d[r[x]]+1$
1. 对于任意一个$x$，$d[x]\leq log(n)$($n$为左偏树的大小)$(N_3)$
---
$(N_3)$
考虑一个节点$x$，会对哪些节点的距离产生贡献，数学归纳可得，如果他对$y$产生了贡献，那么$y$是以满二叉树为基础上建立的二叉树，故$y$的深度每次减$1$,$sz[y]$至少扩大两倍，故得证。
### 左偏树的操作
1. 合并:定义函数$merge(x,y)$为合并以$x$为根的左偏树和以$y$为根的左偏树，返回值为新的树根，如果$a[x]>a[y]$就交换$x,y$，然后递归进行$a[x].r[x]=merge(r[x],y)$，此时如果$d[l[x]]<d[r[x]]$就交换$l[x],r[x]$,最后令$d[x]=d[r[x]]+1$,$return\ x$，时间复杂度为$log(n)$,$(N_4)$
1. 删除：删除$x$，直接$merge(l[x],r[x])$即可，也告诉我们，可以在$log(n)$的时间复杂度删除树上任意一个节点，前提是找得到。
1. 加入一个节点，其实把一个节点看作一棵树，就和$1$一样了。
---
$(N_4)$
时间复杂度证明，其实每次递归发现$d[x],d[y]$其中至少有一个减少了$1$,因此时间复杂度为$O(log(sz[x])+log(sz[y]))$，**也侧面告诉我们不能启发式合并**。
### [模板](https://www.luogu.com.cn/problem/P3377)
## tarjan优化朱刘
### 算法流程
1. 朱刘相当于最小生成树中$B$字开头的算法,而现在介绍的优化，其实相当于$prim$。
1. 枚举每个**原图**中的节点$x$，然后不停地把边$(pre[x],x)$加入最小树形图，答案累加$in[x]$，在某一时刻发现出现了环，删除该环内部所有边，然后暴力把每个指向该环的边$(u,v)$，令边权减去$in[v]$,然后将这个环缩成一个点,然后迭代进行，直至到达根节点$r$，这样还是$O(nm)$。
1. 考虑优化，我们对于每个点$x$建一棵左偏树$T_x$，然后我们就可以在$O(1)$的时间复杂度查询一个节点的最小入边，缩环的时候直接合并左偏树即可，边权减打标记即可,因此我们需要很好的实现标记下放，一次对环的合并我们不妨及做$log(n)$，每个节点属于哪个环可以用并查集路径压缩+按秩合并，删除节点可以用延迟删除$(N_5)$，那么最终时间复杂度不难分析的出来是$O(m+nlog(n))$。
---
$(N_5)$
如果我没记错的话，应该也叫懒惰删除法
### 参考代码
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#define il inline
#define ri register
#define Size 100050
using namespace std;
int fa[Size],cnt,is[Size];
il int find(int);
il void read(int&),Union(int,int);
struct leftist{
struct point{
int l,r,d,v,t,to;
}a[Size]={{0,0,-1,0,0,0}};
int r[Size];
il void merge(int&x,int&y){
if(!x||!y){x^=y;return;}
if(a[x].v>a[y].v)x^=y^=x^=y;
a[y].t-=a[x].t,a[y].v-=a[x].t;
merge(a[x].r,y);
if(a[a[x].l].d<a[a[x].r].d)
a[x].l^=a[x].r^=a[x].l^=a[x].r;
a[x].d=a[a[x].r].d+1;
}
il void spread(int&p){
a[a[p].l].t+=a[p].t,a[a[p].r].t+=a[p].t;
a[a[p].l].v+=a[p].t,a[a[p].r].v+=a[p].t;
a[p].t=0;
}
il void pop(int&x){
spread(x),merge(a[x].l,a[x].r),x=a[x].l;
}
il point*top(int&x){
while(r[x]&&!(find(a[r[x]].to)^x))pop(r[x]);
if(!r[x])puts("-1"),exit(0);
a[r[x]].to=find(a[r[x]].to);
return &a[r[x]];
}
}L;
int pre[Size];
int main(){
int n,m,r,ans(0);leftist::point*temp;
read(n),read(m),read(r),cnt=n,is[r]=r;
for(int i(1),u,v,w;i<=m;++i)
read(u),read(v),read(w),
L.a[i]={0,0,0,w,0,u},
L.merge(L.r[v],u=i);
for(int i(1);i<=n<<1;++i)fa[i]=i;
for(int i(1),j(i);i<=n;j=++i)
while(!is[j]){
while(!is[j])
is[j]=i,j=(temp=L.top(j))->to,
ans+=temp->v;if(is[j]^i)break;
while(~is[j])
is[j]=-1,j=pre[j]=(temp=L.top(j))->to,
temp->t-=temp->v,temp->v=0;++cnt;
while(is[j]^i)is[j]=i,Union(j,cnt),j=pre[j];
j=cnt;
}return printf("%d",ans),0;
}
il void Union(int u,int v){
if((u=find(u))^(v=find(v)))
L.merge(L.r[v],L.r[u]),fa[u]=v;
}
il int find(int x){
return x^fa[x]?fa[x]=find(fa[x]):x;
}
il void read(int&x){
x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
```
## 扩展知识
1. 求没有确定的根的树形图:建立一个超级根$r$，以它为根跑算法,只要将$r$向原图每个点连接一条权值大于原图中所有边的边权的边，这样选这些边肯定不划算，因此只会选择一条。
1. 判无解的奇技淫巧:从小到大依次枚举每个点$i$,加入边$(i,(i+1)\%n+1,+\infty)$,这样如果你最后得到的答案为$+\infty$，那么就无解了。
## 写在后面的话
既然你会$O(E+nlog(n))$，是不是也想谴责luogu为什么放暴力朱刘过了吗？