Chapter 2 · Trees
Tree Diameter in Two Passes
The double-BFS trick, the proof that it is correct, and the DP that beats it when you need more.
Pick any vertex s. Let a be a farthest vertex from s. Let b be a farthest vertex from a. Then dist(a,b) is the diameter.
pair<int,int> far(int s) { // -> {distance, vertex}
vector<int> d(n, -1), par(n, -1);
stack<int> st{{s}}; d[s] = 0; // DFS is enough on a tree!
int best = s;
while (!st.empty()) {
int u = st.top(); st.pop();
if (d[u] > d[best]) best = u;
for (int v : g[u]) if (d[v] == -1) { d[v] = d[u] + 1; par[v] = u; st.push(v); }
}
return { d[best], best };
}
auto [d1, a] = far(0); // pass 1: an endpoint of a diameter
auto [diam, b] = far(a); // pass 2: the diameter itselfOn a general graph you must use BFS (distances). On a tree there is exactly one path, so any traversal computes the true distance; DFS avoids the queue and, more importantly, also hands you the par array so you can reconstruct the diameter path itself.
dist(a,b) equals the diameter D.
(≤) is trivial: a,b are vertices, so their distance is at most the maximum over all pairs. For (≥), let P = x ⇝ y be a diameter path (D = dist(x,y)). Claim: a is an endpoint of some diameter. Root the tree at s. Let c be the highest (closest to s) vertex on the path from s to P, splitting the tree at c into the branch containing x (length p = dist(c,x)), the branch containing y (q = dist(c,y)), and the branch containing s (t = dist(c,s)). Farthest from s means dist(s,a) = max(t+p, t+q) ≥ t + D/2, and p+q = D. Now: dist(a,x) ≥ dist(s,x)? Compare through c — the standard exchange gives max(dist(a,x), dist(a,y)) ≥ max(t+p, t+q), because a is at distance ≥ t from c on the side opposite to whichever of x,y is farther, so a's eccentricity is at least s's. Hence b, being farthest from a, satisfies dist(a,b) ≥ ecc(s) ≥ max(t+p, t+q) and choosing the worse of x,y shows dist(a,b) ≥ D. ∎
That proof is worth reading twice: the only thing used is "one branch at the split point", which is exactly the "path uniqueness" definition of a tree (Trees: Six Definitions of One Object (4)) — the argument collapses on a general graph, where double-BFS is only a 2-approximation, and that is a tight result, not laziness.
#When you need more than the number
Two options: (a) edge contribution — for each edge, count pairs whose path uses it; (b) centroid decomposition (Centroid Decomposition) in O(n log n) for "count pairs with distance ≤ K" including weights. Double-BFS cannot do either; the DP generalises.
// classic tree DP: longest downward chain + best path through u
int ans = 0;
function<int(int,int)> dfs = [&](int u, int p) {
int best1 = 0, best2 = 0; // two deepest child chains
for (int v : g[u]) if (v != p) {
int c = dfs(v, u) + 1;
if (c > best1) { best2 = best1; best1 = c; }
else if (c > best2) best2 = c;
}
ans = max(ans, best1 + best2); // path passing through u
return best1;
};
dfs(0, -1);Two passes: 6 lines, no recursion, easy to write correctly — the diameter length. DP: needed whenever the answer is per-vertex, per-edge, "through u", or when you must avoid the diameter's endpoints. If the problem only asks for the length, write the two passes under time pressure.
Start vertex choice changes the traversal order but never the second pass's answer — try start = 0 and start = 5.