树的直径

hotarugali

发布于 2022-03-03 12:06:04

82700

代码可运行

文章被收录于专栏：hotarugaliの技术分享hotarugaliの技术分享

运行总次数：0

代码可运行

1. 简介

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

2. 思路

2.1 两次 DFS

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

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

如果 $s′$ 或 $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$ 不是直径的端点矛盾。

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

综上可知， $s$ 一定是树的直径的一个端点。推论：树中任意结点的最远点要么是 $s$ ，要么是 $t$ （ $(s,t$ )为树的直径）。证明同上，略。

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

2.2 树形 DP

定义树的高度为树根到所有结点的简单路径的最大值，次高度为树根到所有结点的简单路径第二大的值（ $高度 \geq 次高度$ ）。
对于树中任意一个结点 $v$ ，若 $v$ 到其子树 $l_i$ 中的最远结点的距离为 $L_i$ ，设所有 $L_i$ 中最大的二者为 $L_{1rt} = h_i + (l_i,v)$ 和 $L_{2nd} = h_j + (l_j,v)$ ，对应的 $v$ 的子树为 $l_i$ 和 $l_j$ （没有子树 = 子树对应的 $L_i$ 为零，即没有足够的子树可以看作有 $L_i$ 为零的对应子树），则子树 $v$ 中过结点 $v$ 的最长简单路径等于

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

子树 $v$ 的高度等于

$\begin{array}{c} \max\{L_k = h_k + l_k\} \end{array}$

其中， $k$ 取遍 $v$ 的所有子树， $L_{1rt}$ 和 $L_{2nd}$ 即对应子树 $v$ 的高度和次高度。

由于树的直径一定是以树中某个结点 $v′$ 为根的子树中过结点 $v′$ 的最长简单路径，因此计算每个树结点 $u′$ 的过结点 $u′$ 的最长简单路径，同时维护一下最大值即可。
计算每个树结点 $u′$ 的过结点 $u′$ 的最长简单路径就是一个树形 dp 问题：以当前结点为根的子树的高度和次高度的解取决于其子树的高度，而需要计算的最长简单路径即为 $u′$ 子树的高度和次高度之和。

3. 代码

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

3.1 两次 DFS

#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

#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