树的直径

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

前置知识：树基础。

引入

显然，一棵树可以有多条直径，他们的长度相等。

可以用两次 DFS 或者树形 DP 的方法在时间求出树的直径。

例题

SPOJ PT07Z, Longest path in a tree

给定一棵个节点的树，求其直径的长度。。

做法 1. 两次 DFS

过程

首先从任意节点开始进行第一次 DFS，到达距离其最远的节点，记为，然后再从开始做第二次 DFS，到达距离最远的节点，记为，则即为树的直径。

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

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

证明

使用反证法。记出发节点为。设真实的直径是，而从进行的第一次 DFS 到达的距离其最远的节点不为或。共分三种情况：

若在上：

y 在 s-t 上

有，与为树上任意两节点之间最长的简单路径矛盾。

若不在上，且与存在重合路径：

y 不在 s-t 上，y-z 与 s-t 存在重合路径

有，与为树上任意两节点之间最长的简单路径矛盾。

若不在上，且与不存在重合路径：

y 不在 s-t 上，y-z 与 s-t 不存在重合路径

有，与为树上任意两节点之间最长的简单路径矛盾。

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

负权边

上述证明过程建立在所有路径均不为负的前提下。如果树上存在负权边，则上述证明不成立。故若存在负权边，则无法使用两次 DFS 的方式求解直径。

实现

代码实现如下。

constexpr int N = 10000 + 10;

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;
}

如果需要求出一条直径上所有的节点，则可以在第二次 DFS 的过程中，记录每个点的前序节点，即可从直径的一端一路向前，遍历直径上所有的节点。

做法 2. 树形 DP

过程 1

我们记录当为树的根时，每个节点作为子树的根向下，所能延伸的最长路径长度与次长路径（与最长路径无公共边）长度，那么直径就是对于每一个点，该点能取到的值中的最大值。

树形 DP 可以在存在负权边的情况下求解出树的直径。

实现 1

代码实现如下：

constexpr int N = 10000 + 10;

int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[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);
  printf("%d\n", d);
  return 0;
}

如果需要求出一条直径上所有的节点，则可以在 DP 的过程中，记录下每个节点能向下延伸的最长路径与次长路径（定义同上）所对应的子节点，在求的同时记下对应的节点，使得，即可分别沿着从开始的最长路径的次长路径对应的子节点一路向某个方向（对于无根树，虽然这里指定了为树的根，但仍需记录每点跳转的方向；对于有根树，一路向上跳即可），遍历直径上所有的节点。

过程 2

这里提供一种只使用一个数组进行的树形 DP 方法。

我们定义：以为根的子树中，从出发的最长路径。那么容易得出转移方程：，其中的为的子节点，表示所经过边的权重。

对于树的直径，实际上是可以通过枚举从某个节点出发不同的两条路径相加的最大值求出。因此，在 DP 求解的过程中，我们只需要在更新之前，计算即可算出直径。

实现 2

代码实现如下：

constexpr int N = 10000 + 10;

int n, d = 0;
int dp[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}

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);
  printf("%d\n", d);
  return 0;
}

性质

若树上所有边边权均为正，则树的所有直径中点重合

证明：使用反证法。设两条中点不重合的直径分别为与，中点分别为与。显然，。

无负权边的树所有直径的中点重合

有，与为树上任意两节点之间最长的简单路径矛盾，故性质得证。

习题

最后更新: 2024年10月9日
创建日期: 2020年6月6日