Unofficial Analysis

Solution 1 - DFS Twice

We perform DFS on an arbitrary node and calculate the distance to each node. Since the diameter is the longest path, one of its endpoints must be furthest away from the starting point. Therefore, the node with the maximum distance is one of the endpoints of the diameter. We can run a second DFS from this endpoint, since the maximum distance found will be the diameter.

This approach is Approach 2 in CPH 14.2.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;


vector<int> dist;
vector<vector<int>> adj;


void dfs(int curr, int parent) {
	if (parent != -1) { dist[curr] = dist[parent] + 1; }
	for (int next : adj[curr]) {
		if (next != parent) { dfs(next, curr); }

Java

import java.io.*;
import java.util.*;


public class TreeDiameter {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


		int n = Integer.parseInt(br.readLine());
		int[] dist = new int[n];
		ArrayList<Integer>[] adj = new ArrayList[n];

Python

import sys


input = sys.stdin.readline  # redefine input for performance reasons
sys.setrecursionlimit(10**7)


# iterative DFS necessary in order to AC; recursive TLEs
def iterative_dfs(start):
	dist = [-1] * n
	stack = [start]
	dist[start] = 0

Solution 2 - Tree DP

We first arbitrarily root the tree to establish an order for the nodes. Using DFS, we traverse down from the root and compute the heights of each node's two tallest subtrees. By adding them together in a bottom-up manner, we find the length of the longest path passing through that point. The diameter is the maximum of the longest paths we've found across all nodes.

This DP approach is Approach 1 in CPH.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;


int diameter = 0;
vector<vector<int>> adj;


int dfs(int curr, int parent) {
	int max1 = 0, max2 = 0;
	for (int next : adj[curr]) {
		if (next != parent) {

Java

import java.io.*;
import java.util.*;


public class TreeDiameter {
	private static ArrayList<Integer>[] adj;
	private static int[] height;
	private static int diameter = 0;


	static class State {
		public int node, parent, phase;

Python

import sys


input = sys.stdin.readline  # redefine input for performance reasons
sys.setrecursionlimit(10**7)


n = int(input())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	a, b = map(int, input().split())
	a -= 1

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum