树的直径

1. 简介

树中所有简单路径的最大值即为树的直径,可以通过两次 DFS 或者树形 DP 在 O(n)O(n) 时间内求解。

2. 思路

2.1 两次 DFS

  • 首先将任意一个结点 uu 看作是树根,然后进行 DFS 求出最远的结点 ss;则 ss 一定是树的直径的其中一个端点。

证明

  假设结点 ss'tt' 之间唯一的简单路径为树的直径,(a,b)(a,b) 表示结点 aabb 之间的唯一的简单路径的长度。若该最远点 ss 不是树的直径的一个端点,则对于当前根结点 uu 来说:

  1. 如果 ss'tt' 二者有一个不与 ss 在同一个子树(假设为 tt'),则由于

(s,t)(s,u)+(u,t)(s,u)+(u,t)=(s,t)\begin{array}{c} (s',t') \leq (s',u)+(u,t') \leq (s,u)+(u,t') = (s,t') \end{array}

(s,t)(s',t') 为直径而 ss 不是直径的端点矛盾。

  1. 如果 ss'tt' 均与 ss 在同一个子树,易知树的直径 (s,t)(s',t') 没有经过树根 uu。设该子树根为 uu',则易知 usu' \ne s'utu' \ne t'usu' \ne s,于是 (u,s)(u',s) 一定为子树 uu' 中的最大值,即 ss 为子树 uu' 的最远点,对子树 uu' 同样进行上述分析,以此类推。

综上可知,ss 一定是树的直径的一个端点。

推论:树中任意结点的最远点要么是 ss,要么是 tt(s,t)(s,t) 为树的直径)。

  证明同上,略。

  • 然后将 vv 看作是树根,再进行一次 DFS 求出最远点 tt,则 sstt 之间的简单路径长度即为树的直径。

2.2 树形 DP

  • 定义树的高度为树根到所有结点的简单路径的最大值,次高度为树根到所有结点的简单路径第二大的值(高度 \geq 次高度)。

  • 对于树中任意一个结点 vv,若 vv 到其子树 lil_i 中的最远结点的距离为 LiL_i,设所有 LiL_i 中最大的二者为 L1rt=hi+(li,v)L_{1rt} = h_i + (l_i,v)L2nd=hj+(lj,v)L_{2nd} = h_j + (l_j,v),对应的 vv 的子树为 lil_iljl_j(没有子树 = 子树对应的 LiL_i 为零,即没有足够的子树可以看作有 LiL_i 为零的对应子树),则子树 vv 中过结点 vv 的最长简单路径等于

L1rt+L2nd\begin{array}{c} L_{1rt} + L_{2nd} \end{array}

子树 vv 的高度等于

max{Lk=hk+lk}\begin{array}{c} \max\{L_k = h_k + l_k\} \end{array}

其中,kk 取遍 vv 的所有子树,L1rtL_{1rt}L2ndL_{2nd} 即对应子树 vv 的高度和次高度。

  • 由于树的直径一定是以树中某个结点 vv' 为根的子树中过结点 vv' 的最长简单路径,因此计算每个树结点 uu' 的过结点 uu' 的最长简单路径,同时维护一下最大值即可。

  • 计算每个树结点 uu' 的过结点 uu' 的最长简单路径就是一个树形 dp 问题:以当前结点为根的子树的高度和次高度的解取决于其子树的高度,而需要计算的最长简单路径即为 uu' 子树的高度和次高度之和。

3. 代码

【注】以下模板均是基于无权树求树的直径,有权树只需在前向星中记录一下边权,然后更新结点高度/深度不是 + 1 而是 + 对应边权即可。

3.1 两次 DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

#ifndef _DIAMETEROFTREE_
#define _DIAMETEROFTREE_
#define ll int
#define MAXN 10005

// 树的直径
struct DiameterOfTree{
// 前向星存边
ll cnt; // 动态开点
ll head[MAXN]; // 第一条出边
struct Edge{
ll to; // 边的终点
ll next; // 下一条边
}e[MAXN<<1]; // 存取双向边
// 初始化前向星
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
// 添加双向边
void addEdge(ll u, ll v) {
// 存取双向边
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt++;
e[cnt].next = head[v];
e[cnt].to = u;
head[v] = cnt++;
}
// DFS 求深度最大的结点
ll ans; // 最大深度结点
ll vis[MAXN]; // 标记数组
ll depth[MAXN]; // 深度数组
void dfs(ll u) {
vis[u] = 1;
for(ll i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if(!vis[v]) {
depth[v] = depth[u] + 1;
if(depth[v] > depth[ans]) {
ans = v;
}
dfs(v);
}
}
}
// 求解树的直径
ll getDiameter(ll u) {
// 第一遍 DFS
ans = u;
memset(vis, 0, sizeof(vis));
memset(depth, 0, sizeof(depth));
dfs(u);
// 第二边 DFS
memset(vis, 0, sizeof(vis));
memset(depth, 0, sizeof(depth));
dfs(ans);
return depth[ans];
}
};
#endif

3.2 树形 dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

#ifndef _DIAMETEROFTREE_
#define _DIAMETEROFTREE_
#define ll int
#define MAXN 10005

// 树的直径
struct DiameterOfTree{
// 前向星存边
ll cnt; // 动态开点
ll head[MAXN]; // 第一条出边
struct Edge{
ll to; // 边的终点
ll next; // 下一条边
}e[MAXN<<1]; // 存取双向边
// 初始化前向星
void init() {
cnt = 0;
memset(head, -1, sizeof(head));
}
// 添加双向边
void addEdge(ll u, ll v) {
// 存取双向边
e[cnt].next = head[u];
e[cnt].to = v;
head[u] = cnt++;
e[cnt].next = head[v];
e[cnt].to = u;
head[v] = cnt++;
}
// DFS 树形 dp
ll diameter; // 树的直径
ll vis[MAXN]; // 标记数组
ll dfs(ll u) {
vis[u] = 1;
ll h1 = 0, h2 = 0;
for(ll i = head[u]; i != -1; i = e[i].next) {
ll v = e[i].to;
if(!vis[v]) {
ll h = dfs(v) + 1;
if(h > h1) {
h2 = h1;
h1 = h;
} else if(h > h2) {
h2 = h;
}
}
}
diameter = max(diameter, h1+h2);
return h1;
}
// 求解树的直径
ll getDiameter(ll u) {
diameter = 0;
memset(vis, 0, sizeof(vis));
dfs(u);
return diameter;
}
};
#endif