树的直径与重心

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

注：全文中提到 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},

为了方便理解这个算法，我们画个图  我们选择 $5$ 号点作为随机点 $\text{W}

找到距离它最远的点 4 号点 \text{P}

找到距离 4 号点最远的点 6 号点 \text{Q}

--- 那么如何证明这个定理呢？？？ 首先我们进行分类讨论： **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:

#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} 序上连续的区间时，考虑把两个区间进行合并，

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

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

怎么证明呢

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

其中 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[u]=max(f[u],s[v])

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

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

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

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

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

注意到 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)

时间复杂度 $O(nlog^2n)

3.相关文献

参考文献：

1.YuWenjue的博客

2.forever_dreams的博客

3.fanhq666的博客

4.kai586123的博客

4.后记

~完结撒花~