Tree Diameter

In one sentence

The diameter of a tree is its longest path. Find it with two searches: from any vertex go to the farthest vertex \(u\), then from \(u\) go to the farthest vertex \(v\). The path \(u \to v\) is a diameter.

1. What problem does it solve?

Example — 1881F · Minimum Maximum Distance (5-Graph · G, rating 1700)

A tree has \(n\) vertices, and \(k\) of them are marked. For each vertex \(i\), let \(f_i\) be the largest distance from \(i\) to any marked vertex. Find the smallest \(f_i\) over all vertices.

Limits: \(t \le 10^4\), \(n \le 2 \cdot 10^5\) (sum over tests).

Input          Output
6
7 3
2 6 7          2
1 2
1 3
2 4
2 5
3 6
3 7
4 4
1 2 3 4        2
1 2
2 3
3 4
5 1
1              0
... (3 more tests: 1, 4, 5)

The first test, with marked vertices in brackets:

graph TD
  1((1)) --- 2(["2 marked"])
  1 --- 3((3))
  2 --- 4((4))
  2 --- 5((5))
  3 --- 6(["6 marked"])
  3 --- 7(["7 marked"])

From vertex \(1\): distances to \(2, 6, 7\) are \(1, 2, 2\), so \(f_1 = 2\). From vertex \(6\): distances \(3, 0, 2\), so \(f_6 = 3\). The best is \(2\).

Brute force: BFS from every vertex: \(n\) searches of \(O(n)\) each, \(O(n^2)\). Too slow.

The key idea: find the two marked vertices \(u, v\) that are farthest apart, at distance \(D\) (a "diameter" of the marked vertices). Then the answer is \(\lceil D / 2 \rceil\): stand in the middle of the path \(u - v\). Here \(u = 6\), \(v = 2\) (or \(7\) and \(2\)), \(D = 3\), and \(\lceil 3/2 \rceil = 2\). ✓

Finding \(u\) and \(v\) is exactly the diameter algorithm, restricted to marked vertices.

2. The math

2.1 Distances in a tree

In a tree there is exactly one path between any two vertices (see Graph Concepts). So "the distance" \(\delta(a, b)\) is just the length of that one path, and one BFS from \(a\) gives \(\delta(a, \cdot)\) for every vertex.

2.2 The algorithm

1. BFS from any vertex \(y\). Let \(z\) be a farthest vertex from \(y\).
2. BFS from \(z\). Let \(z'\) be a farthest vertex from \(z\).
3. \(\delta(z, z')\) is the diameter.

For marked vertices, start from a marked \(y\) and only look at marked vertices when choosing "farthest". On the first test, start from \(y = 2\):

BFS from	distances to marked \(2, 6, 7\)	farthest marked
\(2\)	\(0, 3, 3\)	\(z = 6\) (distance 3)
\(6\)	\(3, 0, 2\)	\(z' = 2\) (distance 3)

So \(D = 3\) and the answer is \(\lceil 3 / 2 \rceil = 2\).

2.3 Why the first search lands on an end of a diameter

Theorem. In a tree with non-negative edge lengths, let \(z\) be a vertex farthest from any start \(y\). Then \(z\) is an endpoint of some diameter.

Proof. Let \(s - t\) be a diameter. Because \(z\) is farthest from \(y\), we have \(\delta(y, z) \ge \delta(y, t)\). There are three cases, depending on where \(y\) sits.

Case 1: \(y\) is on the path \(s - t\). Let \(x\) be where the path to \(z\) leaves \(s - t\). Take it on the \(t\) side; the other side is symmetric.

\(\delta(y, z) \ge \delta(y, t)\) and both paths pass through \(x\), so \(\delta(x, z) \ge \delta(x, t)\). Then

\[ \delta(s, z) = \delta(s, x) + \delta(x, z) \;\ge\; \delta(s, x) + \delta(x, t) = \delta(s, t). \]

So \(s - z\) is at least as long as a diameter, which makes it a diameter, with \(z\) as an endpoint.

Case 2: \(y\) is off the path, but the path \(y \to z\) runs along \(s - t\) for a while. It joins at \(x\) and leaves at \(x'\).

Both \(y \to z\) and \(y \to t\) pass through \(x'\), so again \(\delta(x', z) \ge \delta(x', t)\), and \(\delta(s, z) \ge \delta(s, t)\), the same as in Case 1.

Case 3: the path \(y \to z\) does not touch \(s - t\). Let \(x\) on \(s - t\) and \(x'\) on \(y \to z\) be the ends of the path connecting them.

\(\delta(y, z) \ge \delta(y, t) = \delta(y, x') + \delta(x', x) + \delta(x, t)\), so \(\delta(x', z) \ge \delta(x', x) + \delta(x, t)\). Then

\[ \delta(s, z) = \delta(s, x) + \delta(x, x') + \delta(x', z) \;\ge\; \delta(s, x) + 2\,\delta(x, x') + \delta(x, t) \;>\; \delta(s, t), \]

because \(\delta(x, x') \ge 1\). A path longer than the diameter is impossible, so Case 3 never happens. \(\blacksquare\)

The proof only ever compares distances between \(y\), \(z\), \(s\), \(t\). If all four are marked and "farthest" and "diameter" are taken over marked vertices only, every step still holds. So the same two searches find the marked diameter.

Only for non-negative lengths

The proof uses "adding a path never makes things shorter". With negative edge lengths the two-search method can fail.

2.4 Why the answer is \(\lceil D/2 \rceil\)

Let \(u, v\) be marked with \(\delta(u, v) = D\), the largest distance between marked vertices.

No vertex does better. For any \(i\), \(\delta(i, u) + \delta(i, v) \ge \delta(u, v) = D\), so the larger of the two is at least \(D/2\), and since distances are integers, at least \(\lceil D/2 \rceil\). So \(f_i \ge \lceil D/2 \rceil\).

The middle vertex achieves it. Let \(c\) be the vertex on the \(u - v\) path with \(\delta(u, c) = \lceil D/2 \rceil\) and \(\delta(c, v) = \lfloor D/2 \rfloor\). Suppose some marked \(w\) had \(\delta(c, w) > \lceil D/2 \rceil\). The path from \(w\) to \(c\) joins the \(u - v\) path somewhere.

• If it joins on \(u\)'s side of \(c\) (or at \(c\)), the path \(w \to v\) passes through \(c\): \(\delta(w, v) = \delta(w, c) + \delta(c, v) > \lceil D/2 \rceil + \lfloor D/2 \rfloor = D\).
• If it joins on \(v\)'s side, the path \(w \to u\) passes through \(c\): \(\delta(w, u) > 2 \lceil D/2 \rceil \ge D\).

Either way two marked vertices are more than \(D\) apart, a contradiction. So \(f_c \le \lceil D/2 \rceil\). \(\blacksquare\)

2.5 Another way: tree DP (for reference)

Root the tree anywhere. For each vertex \(v\), let \(\text{down}(v)\) be the longest path from \(v\) down into its subtree. The longest path whose highest vertex is \(v\) uses the two largest values of \(\text{down}(c) + 1\) over the children \(c\). The diameter is the best such value over all \(v\). It is also \(O(n)\), and it works with negative lengths.

2.6 From our lesson (March 22)

Lesson notes

For a tree, a standard way to find the diameter is:

1. Start from any node and run DFS or BFS to find a farthest node \(u\).
2. Start from \(u\) and run DFS or BFS again to find a farthest node \(v\).
3. The path from \(u\) to \(v\) is a diameter.

This method is very common and should be remembered.

3. Worked solution — Minimum Maximum Distance

One BFS function, called twice, always choosing the farthest marked vertex. BFS instead of recursive DFS, because a path-shaped tree with \(2 \cdot 10^5\) vertices would overflow Python's recursion.

import sys
from collections import deque

input = sys.stdin.readline


def solve():
    n, k = map(int, input().split())
    marked = list(map(int, input().split()))

    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u, v = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)

    def bfs(start):
        dist = [-1] * (n + 1)
        dist[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist

    d1 = bfs(marked[0])
    u = marked[0]
    for x in marked:
        if d1[x] > d1[u]:
            u = x

    d2 = bfs(u)
    D = 0
    for x in marked:
        D = max(D, d2[x])

    print((D + 1) // 2)


t = int(input())
for _ in range(t):
    solve()

(D + 1) // 2 is \(\lceil D/2 \rceil\) for non-negative integers.

4. What else the two ends give you

Once you have both ends \(u, v\) of a diameter:

• Farthest vertex from any \(x\): it is always \(u\) or \(v\). So \(\max(\delta(x, u), \delta(x, v))\) gives every vertex's farthest distance with just one more BFS.
• The diameter path itself: in the second BFS store parent, then walk back from \(v\) to \(u\) (see BFS).
• The centre: the middle vertex of that path, exactly the \(c\) from §2.4.

5. Common mistakes

Taking the answer from the first BFS

The first BFS starts from an arbitrary vertex, so its farthest distance can be shorter than the diameter. On the first test, the first BFS from \(2\) happens to give \(3\), but starting from \(6\) and stopping would give the wrong vertex pair in other trees.

Choosing the farthest vertex among all vertices

In Minimum Maximum Distance only marked vertices count. An unmarked leaf far away must not be chosen as \(u\).

Recursive DFS on a long path

\(2 \cdot 10^5\) nested calls crash CPython. Use BFS or an explicit stack.

\(D / 2\) instead of \(\lceil D/2 \rceil\)

With \(D = 3\) the middle is not a vertex; the best vertex is \(2\) away from one end. Use (D + 1) // 2.

Using the method with negative weights

See the warning in §2.3.

6. Practice

Problem	Set	Rating	Idea
1881F · Minimum Maximum Distance	5-Graph · G	1700	diameter of marked vertices (this page)
1593E · Gardener and Tree	5-Graph · H	1600	peeling leaves shrinks every long path from both ends
1294F · Three Paths on a Tree	Codeforces	2000	diameter + farthest vertex from the diameter path
911F · Tree Destruction	Codeforces	2400	pair every vertex with a diameter end

---

Credits & licenses

• The three proof figures (§2.3): copied unchanged from OI Wiki — Tree Diameter by the OI Wiki contributors, licensed CC BY-SA 4.0. The proof is translated and adapted from the same page, rewritten with \(\ge\) and with the conclusion made explicit in each case. 911F is from the same page's exercise list.
• Section structure follows USACO Guide — Introduction to Tree Algorithms by Nathan Chen, Siyong Huang and Albert Ye, licensed CC BY-NC-SA 4.0.
• Everything else (the marked-vertex extension, the \(\lceil D/2 \rceil\) proof, worked solution, mistakes) is ours. §2.6 quotes our lesson notes.