树的直径与重心
Erusel
2019-07-07 21:07:39
本篇博客主要讲解树的直径,树的重心以及动态维护
注:全文中提到 $u,v$ 均为特定的,表示 $u,v$ 有一条边相连
**0.前置知识**
简单树形 $\text{dp}$,$\text{dfs}$,线段树,树链剖分,动态点分治(点分树),LCT
**1.树的直径**
**1.0 定义**
给定一棵树,
树中每条边都有一个权值,
树中两点之间的距离定义为连接两点的路径边权之和。
树中最远的两个节点之间的距离被称为树的直径,
连接这两点的路径被称为树的最长链
简单来说,树的直径就是树上一条最长的链的距离
---
对于树的直径,我们普遍有两种做法
一种是贪心两遍 $\text{dfs}$ 或 $\text{bfs}$,另外一种是树形 $\text{dp}$
**1.1 贪心**
考虑这样的贪心策略
对于树上一个随机的点 $W$,
我们找到离它距离最远的 $P$,
找到离 $\text{P}$ 距离最远的点 $\text{Q}$,
$\text{PQ}$ 的距离即为我们要求的直径
为了方便理解这个算法,我们画个图
![2333](https://cdn.luogu.com.cn/upload/pic/62565.png)
我们选择 $5$ 号点作为随机点 $\text{W}$
找到距离它最远的点 $4$ 号点 $\text{P}$
找到距离 $4$ 号点最远的点 $6$ 号点 $\text{Q}$
$\text{PQ}$ 的距离即为我们要求的直径
---
那么如何证明这个定理呢???
首先我们进行分类讨论:
**1.1.0 $\text{W}$ 点在直径上**
如果 $\text{W}$ 号点在直径上,对于其他与 $\text{W}$ 联通的点 $\text{X,Y}$
$\text{XY}=\text{XW}+\text{WY}<\text{PW}+\text{PQ}-\text{PW}=\text{PQ}$
所以 $\text{PQ}$ 最大,证毕
**1.1.1 $\text{W}$ 点不在直径上**
如果 $\text{W}$ 点不在直径上,那 $\text{W}$ 点就没有价值了
这是我们用反证法
我们取一条最长链 $\text{AB(AB!=PQ)}$
接着分类讨论。
**1.1.1.0 $\text{AB}$ 和 $\text{PQ}$ 有交点**
我们设交点为 $\text{C}$。
![2333](https://cdn.luogu.com.cn/upload/pic/62611.png)
因为 $\text{Q}$ 距离 $\text{P}$ 最远,所以 $\text{PQ>PC+CA}$
所以 $\text{CQ>CA}$
所以 $\text{CQ+CB>AC+CB}$
所以 $\text{QB>AB}$
(我们找到了一条比最长链还长的链,推出矛盾)
与 $\text{AB}$ 是最长链矛盾
所以 $\text{PQ}$ 是直径
**1.1.1.1 $\text{AB}$ 和 $\text{PQ}$ 无交点**
我们在 $\text{AB}$ 上取一点 $\text{M}$,在 $\text{PQ}$ 上取一点 $\text{N}$,使得 $\text{MN}$ 联通
![2333](https://cdn.luogu.com.cn/upload/pic/62612.png)
因为 $\text{Q}$ 距离 $\text{P}$ 最远,所以 $\text{PQ>PB}$
所以 $\text{NQ>MN+MB}$
所以 $\text{AM+MN+NQ>AM+MB}$
所以 $\text{AQ>AB}$
(我们又找到了一条比最长链还长的链,推出矛盾)
与 $\text{AB}$ 是最长链矛盾
所以 $\text{PQ}$ 是直径
**code:**
```
#include<bits/stdc++.h>
#define rd(x) x=read()
#define N 20005
using namespace std;
int n,m;
struct E{
int to,nxt,w;
}e[N];
int tot;
int ans,pos;
int head[N],dis[N];
void addEdge(int u,int v,int w){e[++tot].nxt=head[u],e[tot].to=v,e[tot].w=w,head[u]=tot;}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>=10)write(x/10);
putchar(x%10+'0');
}
void dfs(int u,int fa)
{
if(ans<dis[u])ans=dis[u],pos=u;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa)continue;
dis[v]=dis[u]+e[i].w;
dfs(v,u);
}
}
int main()
{
rd(n);
for(int i=1;i<=n-1;i++)
{
int u,v;
rd(u),rd(v);
addEdge(u,v,1);
addEdge(v,u,1);
}
dis[1]=0,dfs(1,0);
ans=0,dis[pos]=0,dfs(pos,0);
cout<<ans<<endl;
return 0;
}
```
---
因为在贪心的证明中,我们依赖于:$x+y>x(y \in R^+)$
**所以使用两遍 $\text{dfs}$ 或 $\text{bfs}$ 的时候,我们要保证边权为正。**
我们已经证明了贪心的正确性,现在考虑 $\text{dp}$
**1.2 树形 $\text{dp}$**
我们考虑用 $f[i]$ 以 $i$ 为根的子树中和从 $i$ 出发的最长长度
考虑以 $u$ 为根的子树
$f[u]=max(f[u],f[v]+e[i].w)$
最长长度就是两条链的和
或者说,我们原来找到了一条 $f[u]$ 的链
现在我们新找到了一条由 $v$ 节点继承的链
这两条链长度之和的最大值即为 $ans$
所以 $ans=max(ans,f[u]+f[v]+e[i].w)$
注意这句话要写在 $f[u]$ 的转移之前
**code:**
```
void dfs(int u,int fa)
{
f[u]=0;
for(int i=head[u];~i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
ans=max(ans,f[u]+f[v]+e[i].w);
f[u]=max(f[u],f[v]+e[i].w);
}
}
```
因为树形 $\text{dp}$ 的做法不需要依赖于 $x+y>x(y \in R^+)$ 的性质,所以边权可以为负
**1.3 树的直径动态维护**
举个例子:
我们需要支持这样的操作:动态查询任意一个子树的直径长度,以及删除一个子树
考虑到每一个子树在 $\text{DFS}$ 序上都是连续的区间,我们可以先搞出整棵树的 $\text{DFS}$ 序,在 $\text{DFS}$ 序上进行操作。
每当我们要查询一个子树的直径长度时,可以使用线段树维护DFS序。
当我们要删除一个在 $\text{DFS}$ 序上连续的区间时,考虑把两个区间进行合并,
左边区间有两个直径端点,右边也有两个,该怎么合并呢?
我们可以利用一个直径的性质,即两个连通块进行合并的时候,就是两个连通块直径的端点(共计四个点)的最远点对。
怎么证明呢
---
假设现在有两个需要合并的连通块(如下图)
![](https://cdn.luogu.com.cn/upload/image_hosting/yhru0o45.png)
其中 $1-2-3-5$ 是一个连通块记作 $A$,$4-6-7$是一个连通块记作$B$
我们要将这两个连通块通过 $1-4$ 联通。
已知 $A$ 连通块内直径长度 $L1$,$B$ 连通块内直径长度 $L2$
我们假设直径不通过 $1-4$,那么最终的长度 $L=max(L1,L2)$,证毕
如果直径通过 $1-4$ ,由前文性质得知,直径的左右端点分别为$1$和$4$在左右子树中能走到最远的点,也符合我们的性质
**注:前文的性质要求边权为正数,所以在这合并两个连通块的时候,我们依旧要求边权为正**
这个性质用途非常广泛,因为我们可以将**点当成一个连通块对待**,在很多题目中都有体现
---
所以线段树维护点对和长度即可
在合并的时候,我们要快速求出两个点之间的距离,需要使用 $\text{LCA}$ 进行计算
时间复杂度为 $O(nlog^2n)$ 可以使用 $\text{RMQ}$ 算法优化 $\text{LCA}$,达到查询 $O(1)$,总体时间 $O(nlogn)$
---
再举个例子,要求支持动态加边,维护直径
简单分析,发现 $\text{LCT}$ 是一个最好的办法,
我们通过可以上文直径的性质,用并查集维护需要加边的点,
用 $\text{LCT}$ 维护直径的左右端点
在添加一条 $u->v$ 的边时,找出 $u,v$ 的祖先 $fx,fy$,算出两边的直径
由于最终的直径端点只可能是 $l[fx],l[fy],r[fx],r[fy]$ 中的一个,暴力枚举即可。
时间复杂度 $O(nlogn)$,只不过常数有点大,大概是6倍左右,还要加上LCT的常数
---
上面介绍了两种不同的思想,一种是线段树维护DFS序,一种是LCT直接维护,
但是都用到了树的直径的性质,请大家牢记这个性质。
---
**2.树的重心**
考虑一个点,以它为根的树中,最大的子树节点数最少,我们把这个点称为树的重心
举个例子,下图中重心为 $1$ 和 $2$
![2333](https://cdn.luogu.com.cn/upload/pic/62751.png)
**2.0 树形dp求重心**
求解树的重心的时候,我们通常会采用树形 $\text{dp}$
我们用 $s[i]$ 代表以 $i$ 为根的子树节点数
$f[i]$ 代表以 $i$ 为根的子树中最大的子树节点个数
显然,$f[u]=max(f[u],s[v])$
但是我们求重心的时候,**是以 $u$ 为根**。
还是举上图的例子,当我们把2号点当成重心时,它就变成了这样
![2333](https://cdn.luogu.com.cn/upload/pic/62758.png)
这时候 $2$ 号节点的~~父亲变成了儿子~~
所以最后统计 $f[u]$ 的时候,还要记得统计 $n-s[u]$ (即以原来父亲为根的子树的节点数)
**code:**
```
void dfs(int u,int fa)
{
s[u]=1,f[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
s[u]+=s[v];
f[u]=max(f[u],s[v]);
}
f[u]=max(f[u],n-s[u]);
}
```
如果题目让我们求多个重心的编号,在最后统计的时候注意一下即可
**code:**
```
#include<bits/stdc++.h>
#define rd(x) x=read()
#define N 20005
using namespace std;
int n,m;
struct E{
int to,nxt;
}e[N];
int tot;
int ans,pos;
int head[N];
int f[N],s[N];
void addEdge(int u,int v){e[++tot].nxt=head[u],e[tot].to=v,head[u]=tot;}
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void write(int x)
{
if(x<0){putchar('-');x=-x;}
if(x>=10)write(x/10);
putchar(x%10+'0');
}
void dfs(int u,int fa)
{
s[u]=1,f[u]=0;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fa)continue;
dfs(v,u);
s[u]+=s[v];
f[u]=max(f[u],s[v]);
}
f[u]=max(f[u],n-s[u]);
}
int main()
{
rd(n);
for(int i=1;i<=n-1;i++)
{
int u,v;
rd(u),rd(v);
addEdge(u,v);
addEdge(v,u);
}
dfs(1,-1);
int minn=1e9;
for(int i=1;i<=n;i++)minn=min(minn,f[i]);
for(int i=1;i<=n;i++)if(f[i]==minn)printf("%d ",i);
printf("\n");
return 0;
}
```
---
**2.1 一些性质**
树的重心有一堆~~稀奇古怪~~好玩的性质
但是一堆终究还是一个
**2.1.0 第一个性质**
把它摆在第一个,也代表它是最重要的性质
考虑上图中的 $2$ 号点
它的子树中节点个数最大的子树是以 $1$ 号点为根的子树
我们考虑以 $1$ 号点为根的子树的根节点,把它作为我们假想的重心,我们把它称为**伪重心**(为了方便说明,这个名词是我造的)
伪重心的子树显然是不平衡的
当我们取伪重心作为重心的时候
设以伪重心为根的子树的节点个数(即原重心最大子树的节点个数)为 $x$,原重心其他子树的节点数之和为 $y$
以伪重心为根,有两棵子树,一颗为 $x-1$,一颗为 $y+1$
我们要保证重心是最优的
所以 $x-1<[(n-1)/2]$
$x<=[n/2]$
这就是第一个性质:
**以重心为根,所有的子树的大小都不超过整个树大小的一半。**
**2.1.1 树的重心最多有两个。**
当一棵树有两个重心时,为了保持尽量平衡,它的第二个重心肯定在以第一个重心为根的最大的子树根节点上。
根据性质1中的证明:当 $x=[n/2]$ 时,这颗树就有两个重心。
**2.1.2 树的重心到其他节点的距离是最小的**
注:相邻两个节点距离为 $1$.
每一次我们一格一格的从重心移动。
假设我们将重心向一棵子树移动,设那颗子树的节点数为 $s$
每移动一格,树的根节点就变化一次。
对于每一次移动,设上一次重心为 $u$
当前重心为 $v$
设$v$的子树节点数为 $s[v]$
$v$ 的子树的每个节点距离重心减少 $1$
其他的所有节点距离重心增加 $1$
设 $ans[u]$ 表示 $u$ 到其他节点的距离
则 $ans[u]=ans[v]+n-s[v]-s[v]=ans[v]+n-2*s[v]$
因为对于重心的每一个节点 $s[i]<=[n/2]$
所以重心到其他节点的距离是最小的。
用上面那个递推式还可以求出距离其他节点最远的节点
**2.1.3 把两个树通过一条边相连得到一个新的树,那么新的树的重心在连接原来两个树的重心的路径上。**
关于这一点的证明较为感性
我们考虑以两棵树的重心为根,即以重心把整棵树提起来。
当我们用一条边把两棵树 $\text{A,B}$ 连接起来时,
我们先考虑树 $\text{A}$
对于树 $\text{A}$, 我们可以理解为树 $\text{A}$ 中的一个节点拥有了所有树$B$的节点
那么整体的中心肯定偏向那一侧
对于树 $\text{B}$,我们也可以这么理解
所以在偏向的过程中,中心可能存在的位置一定在树 $\text{A}$ 重心和树 $\text{B}$ 重心的连线上
**2.1.4 把一个树添加或删除一个叶子,那么它的重心最多只移动一条边的距离。**
这个请读者利用以上性质自行证明
----
**2.2 树的重心动态维护**
考虑添加,删除,移动一片叶子
这三种操作在[fanhq666的博客](http://fanhq666.blog.163.com/blog/static/81943426201172472943638)
都有简单的说明
可惜原博客的链接挂了,这里有个新的[链接](https://www.cnblogs.com/qlky/p/5781081.html)
而我们关注的,是更加详细的做法
注意到 fhq 大爷的博客里有这么一句话
> 定义稍微广义的树的重心:每个点有一个非负权,每个边有个正的长度,到所有点的权乘以距离的和最小的点定义为重心。
我们先不考虑移动一片叶子,对于添加一片叶子,就是把一片叶子的点权改为1,删除一片叶子,就是把一片叶子的点权改为 $0$
考虑假设我们要维护广义中心的点权(加减一个值),
如果我们解决了上面这个问题,我们就可以维护添加和删除了
动态点分治(点分树)固然可做,这里提供一种树链剖分的方法.
**即使我们把重心的定义广义化了,**
**重心依旧不依赖于边权**
回顾一下原定义:
> **考虑一个点,以它为根的树中,最大的子树节点数最少,我们把这个点称为树的重心**
这里,我们要把节点数改为节点权值总和
这里证明一下:
我们用类似证明性质 $2.1.2$ 的方法,考虑从重心移动一次
我们用 $w(u,v)$ 表示 $u->v$ 的距离, $e(u)$ 表示 $u$ 的点权, $f(u)$ 表示总和
定义 $f(u)=\sum e(v)*w(u,v)$
因为这是一颗无根树,所以我们以最大的子树节点权值总和最小的点 $u$ 为根, $size_i$ 表示 $u$ 节点的第 $i$ 个子树的大小,$s_i$ 表示 $size_i$ 表示 $u$ 节点的第 $i$ 个子树
移动一条边之后,设$u'$是$u$的第$k$个子树的根节点,
$f(u')=f(u)-\sum e(v)(v \in s_i)+\sum e(v)(v \notin s_i)$
因为保证了 $\sum e(v)(v \in s_i)<=[\sum e(v)/2]$
所以 $f(u')>=f(u) $
所以 $f(u)$ 是最优的。
---
因为一条链上深度越大 $\text{dfs}$ 序越大,
所以根据这个性质,我们只要找到一个点 $u$ ,
使得 $f(u)*2>=f(rt)$,且 $u$ 节点最深
这个可以在线段树上利用二分快速找出。
我们用 $cost$ 表示花费,$e(v),w(u,v)$ 的定义同上
$cost=\sum e(v)*w(u,v)$
对于 $w(u,v)$ 我们可以用LCA维护:
$w(u,v)=w(u,rt)+w(v,rt)-2*w(lca,rt)$
则原式可化为:
$cost=\sum w(u,rt)*e(v)+\sum w(v,rt)*e(v)-2*w(lca,rt)*e(v)$
在更新的时候,记录一下 $\sum \Delta e$ 和 $\sum \Delta w(u,rt)*e$即可,时间复杂度 $O(1)$
对于 $w(lca,rt)*e(v)$ 每一次更新时,我们都从当前节点到根节点的大小$size$一路修改
查询时,即查询 $\sum (w(u,rt)-w(fa[u],rt))*size(u)$
$w(u,rt)-w(fa[u],rt)$ 用线段树维护即可
时间复杂度 $O(nlog^2n)$
**3.相关文献**
参考文献:
1.[YuWenjue的博客](https://www.cnblogs.com/ywjblog/p/9254997.html)
2.[forever_dreams的博客](https://blog.csdn.net/forever_dreams/article/details/81051578)
3.[fanhq666的博客](http://fanhq666.blog.163.com/blog/static/81943426201172472943638)
4.[kai586123的博客](https://kai586123.blog.luogu.org/solution-p3345)
**4.后记**
~完结撒花~