

树的直径

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

前置知识：树基础。

例题¶

例题 SPOJ PT07Z, Longest path in a tree 。

做法 1. 两次 DFS¶

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

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

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

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

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

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

当出发结点在时，假设到达的最远结点不是中的任一个。这时将与不与之重合的拼接（也可以假设不与之重合的是直径的另一个方向），可以得到一条更长的直径，与前提矛盾。
当出发结点不在上时，分两种情况：
- 当到达的最远结点横穿时，记与之相交的结点为。此时有。而此时，故可得。由 1 的结论可知该假设不成立。
- 当到达的最远结点与不相交时，记到的最短路首先与相交的结点是。由假设。而又可以形成，而，与题意矛盾。

因此定理成立。

const int N = 10009;
VI adj[N];
int d[N], c;
int n;
#define v (*it)
void dfs(int u) {
  ECH(it, adj[u]) if (!d[v]) {
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v);
  }
}
#undef v
int main() {
  REP_C(i, RD(n) - 1) {
    int a, b;
    RD(a, b);
    --a, --b;
    adj[a].PB(b), adj[b].PB(a);
  }

  d[0] = 1, dfs(0);
  RST(d), d[c] = 1, dfs(c), OT(d[c] - 1);
}

做法 2. 树形 DP¶

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

#include <iostream>
#include <vector>
using namespace std;

const int N = int(1e4) + 9;
vector<int> adj[N];
int n, d;
int dfs(int u = 1, int p = -1) {
  int d1 = 0, d2 = 0;
  for (auto v : adj[u]) {
    if (v == p) continue;
    int d = dfs(v, u) + 1;
    if (d > d1)
      d2 = d1, d1 = d;
    else if (d > d2)
      d2 = d;
  }
  d = max(d, d1 + d2);
  return d1;
}
int main() {
  cin >> n;
  for (int i = 0; i < n - 1; ++i) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs();
  cout << d << endl;
}

习题¶

Last update and/or translate time of this article，Check the history
Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
Contributor of this article OI-wiki
Translator of this article Visit the original article!
The article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

树的直径

例题¶

做法 1. 两次 DFS¶

做法 2. 树形 DP¶

习题¶

Comments