Skip to content

Tree Diameter

The longest simple path between any two nodes in a tree is called the diameter of the tree.

Prerequisite: Tree Basics.

Introduction

Clearly, a tree can have multiple diameters, all of equal length.

The diameter of a tree can be found in \(O(n)\) time using either two DFS traversals or tree DP.

Two DFS Traversals

First, start a DFS from any node \(y\) to reach the farthest node from it, denoted as \(z\). Then, start a second DFS from \(z\) to reach the farthest node from \(z\), denoted as \(z'\). Then \(\delta(z,z')\) is the diameter of the tree.

Obviously, if the node \(z\) reached in the first DFS is one end of a diameter, then the node \(z'\) reached in the second DFS must be the other end. We only need to prove that in any case, \(z\) must be one end of a diameter.

Theorem: On a tree, starting a DFS from any node \(y\) and reaching the farthest node \(z\) from it guarantees that \(z\) is one end of a diameter.

Proof

Proof by contradiction. Let the starting node be \(y\). Suppose the true diameter is \(\delta(s,t)\), and the farthest node \(z\) reached from \(y\) in the first DFS is neither \(t\) nor \(s\). There are three cases:

  • If \(y\) lies on \(\delta(s,t)\):

y on s-t

We have \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), contradicting that \(\delta(s,t)\) is the longest simple path between any two nodes in the tree.

  • If \(y\) is not on \(\delta(s,t)\), and \(\delta(y,z)\) shares a common path with \(\delta(s,t)\):

y not on s-t, y-z overlaps with s-t

We have \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), contradicting that \(\delta(s,t)\) is the longest simple path between any two nodes in the tree.

  • If \(y\) is not on \(\delta(s,t)\), and \(\delta(y,z)\) does not share any common path with \(\delta(s,t)\):

y not on s-t, y-z disjoint from s-t

We have \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x',z) > \delta(x',t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\), contradicting that \(\delta(s,t)\) is the longest simple path between any two nodes in the tree.

In all three cases, the assumption leads to a contradiction. Therefore, the theorem holds.

Negative Edge Weights

The above proof assumes all path weights are non-negative. If the tree contains edges with negative weights, the proof fails. Hence, the two DFS method cannot be used to find the diameter when negative edge weights exist.

If we need to retrieve all nodes on a diameter, we can record the predecessor of each node during the second DFS. Then, starting from one end of the diameter, we can traverse all nodes along the diameter by following the predecessor chain.

Tree DP

Method 1

When rooting the tree at node \(1\), for each node \(u\) as the root of its subtree, we record the length of the longest downward path \(d_1\) and the length of the second longest downward path \(d_2\) that does not share any edge with the longest path. The diameter is then the maximum value of \(d_1 + d_2\) over all nodes.

Tree DP can find the diameter even when negative edge weights exist.

If we need to retrieve all nodes on a diameter, during the DP process, we can record for each node the child nodes corresponding to its longest and second longest downward paths (as defined above). While computing \(d\), we also record the node \(u\) such that \(d = d_1[u] + d_2[u]\). Then, starting from \(u\), we can traverse along the directions of its longest and second longest paths (for an unrooted tree, even though we rooted at \(1\), we still need to record the direction to jump; for a rooted tree, simply move upward) to visit all nodes on the diameter.

Method 2

Here we provide a tree DP method that uses only one array.

We define \(dp[u]\) as the length of the longest path starting from \(u\) within its subtree. The transition is straightforward: \(dp[u] = \max(dp[u], dp[v] + w(u, v))\), where \(v\) is a child of \(u\) and \(w(u, v)\) is the weight of the edge.

For the tree diameter, it can actually be computed by enumerating the maximum sum of two different paths starting from each node. Therefore, during the DP process, before updating \(dp[u]\), we compute \(d = \max(d, dp[u] + dp[v] + w(u, v))\) to obtain the diameter \(d\).

Examples

Luogu B4016 Tree Diameter

Given a tree with \(n\) nodes, find the length of its diameter. \(1\leq n\leq 10^5\).

Reference Implementation for Two DFS 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 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;
}
Reference Implementation for Tree DP with Two Arrays 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 10;

int n, d;
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;
}
Reference Implementation for Tree DP with One Array 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 100000 + 10;

int n, d;
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;
}

Properties

The diameter of a tree has the following property: If all edge weights in the tree are positive, then the midpoints of all diameters coincide.

Proof

Proof by contradiction. Suppose there are two diameters \(\delta(s,t)\) and \(\delta(s',t')\) with non-coinciding midpoints \(x\) and \(x'\), respectively. Clearly, \(\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')\).

Midpoints coincide for trees with non-negative edge weights

Then \(\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)\), contradicting that \(\delta(s,t)\) is the longest simple path between any two nodes in the tree. Hence, the property holds.

Exercises

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