树的直径与重心

本篇博客主要讲解树的直径，树的重心以及动态维护

注：全文中提到

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}

的距离即为我们要求的直径

为了方便理解这个算法，我们画个图

我们选择

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}

。

因为

\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}

联通

因为

\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:

CPP

#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:

CPP

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}

序上连续的区间时，考虑把两个区间进行合并，

左边区间有两个直径端点，右边也有两个，该怎么合并呢？

我们可以利用一个直径的性质，即两个连通块进行合并的时候，就是两个连通块直径的端点（共计四个点）的最远点对。

怎么证明呢

假设现在有两个需要合并的连通块（如下图）

其中

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

2.0 树形dp求重心

求解树的重心的时候，我们通常会采用树形

\text{dp}

我们用

s[i]

代表以

i

为根的子树节点数

f[i]

代表以

i

为根的子树中最大的子树节点个数

显然，

f[u]=max(f[u],s[v])

但是我们求重心的时候，是以 $u$ 为根。

还是举上图的例子，当我们把2号点当成重心时，它就变成了这样

这时候

2

号节点的~~父亲变成了儿子~~

所以最后统计

f[u]

的时候，还要记得统计

n-s[u]

(即以原来父亲为根的子树的节点数)

code:

CPP

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:

CPP

#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的博客都有简单的说明

可惜原博客的链接挂了，这里有个新的链接

而我们关注的，是更加详细的做法

注意到 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.相关文献

参考文献：

4.后记

~完结撒花~

文章操作

相关推荐

评论

树的直径与重心