跳转至

树论-树的直径

树的直径是树上任意两点间最长的简单路径。

例题

B4016 树的直径

题目描述

给定一棵 \(n\) 个结点的树，树没有边权。请求出树的直径是多少，即树上的最长路径长度是多少。

做法

  • 两遍DFS/BFS -只适用于非负边权

首先从任意一点 \(x\) 开始进行第一次DFS/BFS，到达距离其最远的点 \(u\) ， \(u\) 为直径的端点，然后再从 \(u\) 开始进行第二次DFS/BFS，到达距离其最远的点 \(v\) ， \(v\) 为直径的另一端点，此时路径 \((u,v)\) 即为树的直径。

为什么从任意一点 \(x\) 开始进行一次DFS/BFS，到达距离其最远的点 $y $ 为直径的端点 \(u\) 呢？

使用反证法进行分类讨论即可。

假设 \(y\) 不是直径的端点 \(u\) 。

  1. \(x\) 在直径 \((u,v)\) 上。

  2. \(x\) 不在直径 \((u,v)\) 上，且路径 \((x,y)\) 与 直径 \((u,v)\) 有重合路径。

  3. \(x\) 不在直径 \((u,v)\) 上，且路径 \((x,y)\) 与 直径 \((u,v)\) 没有重合路径。

请读者自行画棵树进行分类讨论，尝试推出下面的不等式。

我们会推出 \(dis(y,v)>dis(u,v)\) 这个不等式，与直径的定义矛盾，所以假设不成立。

  • 树形DP -适用于所有情况

将任意一点定为树的根。

在一棵以 \(x\) 为根的子树上，记录 \(d1_x\) 为 \(x\) 向下延伸的最长路径的长度， \(d2_x\) 为 \(x\) 向下延伸的次长路径的长度，这个次长路径与最长路径没有重合路径。

那么直径就是 \(\max_{i=1}^{n}d1_i+d2_i\) 。

代码

  • DP核心代码：
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
void dp(int x,int fa){
    for (int i=0;i<g[x].size();i++){
        int y=g[x][i];
        if (y==fa)continue;
        dp(y,x);
        f[x]=max(f[x],d[x]+d[y]+1);
        d[x]=max(d[x],d[y]+1);
        // 1 为本题的边权
    }
}

性质

边权大小均非负，下列所有性质才成立。

1.直径两端点一定是两个叶子节点。

2.树的所有直径中点重合。

证明：使用反证法。

3.距离任意点最远的点一定是直径的一个端点。

证明：使用反证法

4.对于两棵树，第一棵树的直径为 \((a,b)\) ，第二棵树的直径为 \((c,d)\) ，用一条边将两棵树连接，这棵新树的直径端点一定是 \(a,b,c,d\) 中的两个。

证明：如果新树直径不是原来两棵树中一棵的直径，那么新直径一定经过两棵树的连接边，新直径在原来每棵树中的部分一定是距离连接点最远的点，即一定是原树直径的一个端点。

5.对于一棵树，如果在一个点上接一个叶子节点，那么最多会改变直径的一个端点。

题单

P4408 [NOI2003] 逃学的小孩

直径为 \((x,y)\) 。

容易发现答案为 $$ \max_{i=1}^n (\min(dis(x,i),dis(y,i))+dis(x,y)) $$

P2491 [SDOI2011] 消防 + P1099 [NOIP2007 提高组] 树网的核

P2195 HXY造公园

P2056 [ZJOI2007] 捉迷藏

  • 利用性质4，用线段树来维护直径的长度，以及左右端点即可。
  • 用点分树做，维护三个堆。

P3629 [APIO2010] 巡逻

Problem - F

未完待续？