AIOJ

The longest simple path between any two vertices of a tree is called the tree's diameter.

Introduction

Clearly, a tree may have multiple diameters, all with the same length.

The tree's diameter can be found in $O(n)$ time either by running DFS twice or by using tree DP.

Two DFS traversals

First, run a DFS from any vertex $y$ and let $z$ be the vertex reached at the greatest distance. Then run a second DFS from $z$ ; the vertex reached at the greatest distance from $z$ is denoted by $z'$ , so $\delta(z,z')$ is the tree's diameter.

Clearly, if the vertex $z$ reached by the first DFS is an endpoint of a diameter, the vertex $z'$ reached by the second DFS is necessarily the other endpoint. We only need to prove that $z$ must be an endpoint of a diameter in every case.

Theorem: Starting from any vertex $y$ in a tree, a DFS that reaches the vertex $z$ farthest from it must reach an endpoint of a diameter.

Proof

We use contradiction. Let the starting vertex be $y$ . Let the actual diameter be $\delta(s,t)$ , and suppose that the farthest vertex reached by the first DFS from $y$ is $z$ , and that this vertex is neither $t$ nor $s$ . There are three cases.

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

y lies 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 the fact that $\delta(s,t)$ is the longest simple path between any two vertices of the tree.

If $y$ does not lie on $\delta(s,t)$ and $\delta(y,z)$ shares a path with $\delta(s,t)$ :

y is not on s-t, and y-z shares a path with s-t

Again, $\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)$ , contradicting the fact that $\delta(s,t)$ is the longest simple path between any two vertices of the tree.

If $y$ does not lie on $\delta(s,t)$ and $\delta(y,z)$ shares no path with $\delta(s,t)$ :

y is not on s-t, and y-z shares no path with 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 the fact that $\delta(s,t)$ is the longest simple path between any two vertices of the tree.

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

Negative edge weights

The proof above assumes that every path has nonnegative total weight. If the tree contains a negative-weight edge, the proof no longer holds. Therefore, when negative-weight edges are present, the diameter cannot be found by the two-DFS method.

If we need all vertices on one diameter, record each vertex's predecessor during the second DFS. We can then walk from one endpoint toward the starting point and enumerate every vertex on the diameter.

Tree DP

Method 1

Root the tree at vertex $1$ . For each vertex, record the length $d_1$ of the longest path that extends downward from it and the length $d_2$ of the second-longest path that shares no edge with the longest path. The diameter is the maximum value of $d_1 + d_2$ over all vertices.

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

If all vertices on one diameter are required, record during the DP the child corresponding to each vertex's longest and second-longest downward path (as defined above). While finding $d$ , also record the vertex $u$ satisfying $d = d_1[u] + d_2[u]$ . Then follow the child corresponding to the longest path from $u$ and the child corresponding to the second-longest path in their respective directions. For an unrooted tree, although $1$ was chosen as the root, the direction of every jump must still be recorded; for a rooted tree, one side can simply be followed upward. This enumerates every vertex on the diameter.

Method 2

Here is a tree-DP method that uses only one array.

Define $dp[u]$ as the longest path starting from $u$ within the subtree rooted at $u$ . 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 traversed.

The tree's diameter can be obtained by maximizing the sum of two different paths starting from the same vertex. Therefore, during the DP, before updating $dp[u]$ , compute $d = \max(d, dp[u] + dp[v] + w(u, v))$ ; this gives the diameter $d$ .

Example

Luogu B4016 Tree Diameter

Given a tree with $n$ vertices, find the length of its diameter. $1\leq n\leq 10^5$ .

Reference implementation using two DFS traversals

#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 of tree DP with two arrays

#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 of tree DP with one array

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

Property

Tree diameters have the following property: if every edge of a tree has positive weight, the midpoints of all its diameters coincide.

Proof

We use contradiction. Let two diameters with distinct midpoints be $\delta(s,t)$ and $\delta(s',t')$ , with midpoints $x$ and $x'$ , respectively. Clearly, $\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')$ .

All diameters of a tree without negative edge weights have the same midpoint

We have $\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)$ , contradicting the fact that $\delta(s,t)$ is the longest simple path between any two vertices of the tree. Hence the property follows.