树的直径——直径的性质

· · 算法·理论

一.定义

树的直径：树上任意两节点之间最长的简单路径即为树的直径。

一棵树可以有多条直径，他们的长度相等。如下图： 6——5 是一条树的直径，7——5 也是一条树的直径

二.求解树的直径

1.方法一:(两次DFS求解)

前提条件：树中边权不能是负数

  1. 首先从任意节点 z 开始进行第一次 DFS ，到达距离其最远的节点,记为 x

  2. 然后再从 开始做第二次 DFS ，到达距离 x 最远的节点，记为 y ，则 S(x,y) 即为树的直径。

(1)过程示意图：

(2)正确性证明

显然，如果第一次 DFS 到达的节点 x 是直径的端，那么第二次DFS到达的节点 y 一定是直径的一端。我们只需证明在任意情况下，x 必为直径的端。

即：算法第一步找到的节点 x 如果是直径的一个端点，那么算法的第二步找到的节点 y 也一定是直径的令外一个端点，即证明第一步正确即可。

定理：在一棵树上，从任意节点 z 开始进行一次 DFS ,到达的距离其最远的节点 x 必为直径的端。

证明：使用反证法，记出发点 z。树真实的直径记为 S(s,t),假设从节点 z 出发到达距离其最远的节点 不为 t 或 z 。

按照出发点 z 的位置进行分类讨论，分为如下三种情况:

有 S(z,x) > S(z,t) \Rightarrow S(v,x) > S(v,t) \Rightarrow S(s,x) > S(s,t) ，与 S(s,t) 为树上任意两节点之间最长的简单路径

综上，三种情况下假设均会产生矛盾，故定理得证。

解释：前提条件：树中边权不能是负数

如果边权为负数，则以上第三种情况不能证明出来。如下图：

(3)代码实现

int n, c, d[N];
vector<int> E[N];
void dfs(int u, int fa) {
    for (int v : E[u]) {
        if (v == fa) continue;
        d[v] = d[u] + 1;
        if (d[v] > d[c]) c = v;
        dfs(v, u);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        E[u].push_back(v), E[v].push_back(u);
    }
    dfs(1, 0);
    d[c] = 0, dfs(c, 0);
    printf("%d\n", d[c]);
    return 0;
}

2.方法二:(树形DP)

备注：树中边权可以是负数，也可以是正数

  1. 符号定义
 d1[u] :表示节点 u 向下延伸的最大路径长度
 d2[u] :表示节点 u 向下延伸的次大路径长度
 f[u] :表示以节点 u 为根的子树并经过节点 u 的最长的路径长度

  1. 状态转移： f[u]=d1[u]+d2[u]

  2. 代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int h[N], e[N], ne[N], w[N], idx = 1;
int f[N], n, res;
int d1[N], d2[N];
void dfs(int u, int fa) {
    d1[u] = d2[u] = 0;
    for(int i=h[u];i;i=ne[i]){
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u);
        int t = d1[v] + w[i];
        if (t > d1[u])
        d2[u] = d1[u], d1[u] = t;
        else if (t > d2[u])
        d2[u] = t;
    }
    f[u] = d1[u] + d2[u];
}
void add(int u, int v, int z)
{
    e[idx] = v;
    w[idx] = z;
    ne[idx] = h[u];
    h[u] = idx++;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v,w;
        scanf("%d%d%d", &u, &v,&w);
        add(u, v, w);
        add(v, u, w);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    printf("%d\n", res);
    return 0;
}
  1. 如果需要求出条直径上所有的节点，则可以在 DP 的过程中，记录下每个节点能向下延伸的最长路径与次长路径（定义同上）所对应的子节点，在求 d 的同时记下对应的节点u,使得 d=d1[u]+d2[u] ,即可分别沿着从 u 开始的最长路径的次长路径对应的子节点一路向某个方向(对于无根树，虽然这里指定了 1 为树的根，但仍需记录每点跳转的方向；对于有根树，一路向上跳即可），遍历直径上所有的节点。

三.树的直径的性质

部分证明作者懒得打，可以看this