树的直径

1. 简介

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

2. 思路

2.1 两次 DFS

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

证明

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

  1. 如果 s′s' 或 t′t' 二者有一个不与 ss 在同一个子树（假设为 t′t'），则由于

(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. 如果 s′s'、t′t' 均与 ss 在同一个子树，易知树的直径 (s′,t′)(s',t') 没有经过树根 uu。设该子树根为 u′u'，则易知 u′≠s′u' \ne s' 且 u′≠t′u' \ne t' 且 u′≠su' \ne s，于是 (u′,s)(u',s) 一定为子树 u′u' 中的最大值，即 ss 为子树 u′u' 的最远点，对子树 u′u' 同样进行上述分析，以此类推。

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

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

  证明同上，略。

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

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_i 和 ljl_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 的高度和次高度。

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

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

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