Tree Diameter
You are given a tree with \(n\) nodes. The diameter of a tree is the largest distance between two of its nodes, where the distance is the number of edges on the path between them.
Find the diameter of the tree.
Constraints:
- \(1 \le n \le 2 \cdot 10^5\)
- \(1 \le a, b \le n\)
Input:
- First line: integer \(n\). The nodes are numbered \(1, 2, \ldots, n\).
- Next \(n - 1\) lines: two integers \(a\) and \(b\) — an edge between nodes \(a\) and \(b\).
Output:
- One integer — the diameter.
Example:
Input:
5
1 2
1 3
3 4
3 5
Output:
3
(The path \(2 \to 1 \to 3 \to 5\) has \(3\) edges.)
Solution
Trying all pairs of nodes is too slow. Instead, we use two DFS runs:
- Run DFS from any node, for example node \(1\), and compute the depth of every node. Let \(a\) be the deepest node.
- Run DFS from \(a\). Let \(b\) be the deepest node now. The depth of \(b\) is the diameter.
Why does this work? The second DFS finds the longest path that starts at \(a\). So it is enough to show that \(a\) is an end of some diameter.
Let \(d(x, y)\) be the distance between nodes \(x\) and \(y\). Let \(u\)–\(v\) be a diameter, with length \(D = d(u, v)\), and let \(c\) be the node of the path \(u\)–\(v\) that is closest to node \(1\). The path from node \(1\) to any node of the path \(u\)–\(v\) first reaches it at \(c\). A tree has no cycles, so once a path leaves the path \(u\)–\(v\), it cannot come back to it. There are two cases for the path from node \(1\) to \(a\).
- It does not touch the path \(u\)–\(v\). Let \(p\) be the last node that it shares with the path from \(1\) to \(c\); then \(p \ne c\). Node \(a\) is the farthest node from node \(1\), so \(d(1, a) \ge d(1, v)\), that is, \(d(1, p) + d(p, a) \ge d(1, p) + d(p, c) + d(c, v)\). So \(d(p, a) \ge d(p, c) + d(c, v)\). The path from \(u\) through \(c\) and \(p\) to \(a\) then has length \(d(u, c) + d(c, p) + d(p, a) \ge D + 2 \cdot d(c, p) > D\). This is impossible, because no path is longer than a diameter.
- It touches the path \(u\)–\(v\). It enters at \(c\), may continue along the path \(u\)–\(v\), and leaves it at a node \(q\) (or ends there, if \(a = q\)). We name the ends so that \(q\) is between \(c\) and \(v\). Then \(d(1, a) = d(1, q) + d(q, a)\) and \(d(1, v) = d(1, q) + d(q, v)\), so \(d(1, a) \ge d(1, v)\) gives \(d(q, a) \ge d(q, v)\). The path from \(u\) to \(a\) goes through \(q\), so its length is \(d(u, q) + d(q, a) \ge d(u, q) + d(q, v) = D\). So the path \(u\)–\(a\) is also a diameter.
In both cases, \(a\) is an end of a diameter.
For the example: DFS from node \(1\) gives depth \(2\) for nodes \(4\) and \(5\), so \(a = 4\). DFS from node \(4\) gives depth \(3\) for node \(2\), so the diameter is \(3\).
The time complexity is \(O(n)\).
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> adj;
vector<int> depth;
void dfs(int v, int p) {
for (int to : adj[v]) {
if (to == p) continue;
depth[to] = depth[v] + 1;
dfs(to, v);
}
}
// returns the node that is farthest from start
int farthest(int start, int n) {
depth[start] = 0;
dfs(start, 0);
int best = start;
for (int v = 1; v <= n; v++) {
if (depth[v] > depth[best]) best = v;
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
adj.resize(n + 1);
depth.resize(n + 1);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
int a = farthest(1, n); // a is one end of a diameter
int b = farthest(a, n); // b is the other end
cout << depth[b] << "\n";
}