A tree is a connected acyclic undirected graph: n nodes, n-1 edges, unique path between any pair. The diameter is the maximum number of edges (or the maximum weighted length) on any simple path.
CSES Tree Diameter. The two-sweep proof: let u be farthest from an arbitrary root. u is an endpoint of some diameter. Then the farthest from u is the other endpoint.
Constraints: n ≤ 2·10⁵ so you get two linear DFS, not all-pairs. Floyd is O(n³) and does not exist.
function farthest(start, adj) {
const n = adj.length;
const dist = Array(n).fill(-1);
const stack = [[start, 0]];
dist[start] = 0;
let best = start;
while (stack.length) {
const [u, d] = stack.pop();
if (d > dist[best]) best = u;
for (const v of adj[u]) {
if (dist[v] === -1) {
dist[v] = d + 1;
stack.push([v, d + 1]);
}
}
}
return { node: best, dist };
}
function treeDiameter(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u);
}
const u = farthest(0, adj).node;
const { dist } = farthest(u, adj);
return Math.max(...dist);
}Checks 0/2