

树的直径

图中所有最短路径的最大值即为「直径」，可以用两次 DFS 或者树形 DP 的方法在 O(n) 时间求出树的直径。

前置知识：树基础。

例题¶

SPOJ PT07Z, Longest path in a tree

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

做法 1. 两次 DFS¶

首先对任意一个结点做 DFS 求出最远的结点，然后以这个结点为根结点再做 DFS 到达另一个最远结点。第一次 DFS 到达的结点可以证明一定是这个图的直径的一端，第二次 DFS 就会达到另一端。下面来证明这个定理。

但是在证明定义之前，先证明一个引理：

引理：在一个连通无向无环图中，、和是三个不同的结点。当到的最短路与到的最短路不重合时，到的最短路就是这两条最短路的拼接。

证明：假设到有一条不经过的更短路，则该路与、形成一个环，与前提矛盾。

定理：在一个连通无向无环图中，以任意结点出发所能到达的最远结点，一定是该图直径的端点之一。

证明：假设这条直径是。分两种情况：

当出发结点在时，假设到达的最远结点不是中的任一个。这时将与不与之重合的拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。
当出发结点不在上时，分两种情况：
- 当到达的最远结点横穿时，记与之相交的结点为。此时有。而此时，故可得。由 1 的结论可知该假设不成立。
- 当到达的最远结点与不相交时，定义从开始到结束的简单路径上，第一个同时也存在于简单路径上的结点为，最后一个存在简单路径上的节点为。如下图。

那么我们可以列出一些式子如下：

那么根据假设，有。既然这样子的话，那么，和对应着直径这一前提不符，故的最远节点不可能在到这个直径对应的路外面。

当 y 不在 s-t 上，且 z 也不在的情况

因此定理成立。

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

做法 2. 树形 DP¶

我们记录当为树的根时，每个节点作为子树的根向下，所能延伸的最远距离，和次远距离，那么直径就是所有的最大值。

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

习题¶

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

树的直径

例题¶

做法 1. 两次 DFS¶

做法 2. 树形 DP¶

习题¶

评论