Разбор

Выполним поиск в глубину, начиная с любой вершины, например, с вершины $1$. Найдём вершину, наиболее удалённую от $1$, и обозначим её как вершину $a$. Затем запустим поиск в глубину из вершины $a$ и найдём вершину, которая будет наиболее удалённой от $a$. Обозначим её как вершину $b$. Тогда расстояние между вершинами $a$ и $b$ будет максимальным и равно диаметру дерева.

Пример

Рассмотрим дерево из примера.

Диаметр дерева равен $3$. Наибольшее расстояние достигается, например, для вершин $2$ и $5$.

Упражнение

Найдите диаметр дерева.

Реализация алгоритма

Входное дерево храним в списке смежности $g$. Кратчайшие расстояния от источника до вершин сохраняем в массиве $dist$.

vector<vector<int>> g;
vector<int> dist;

Функция dfs выполняет поиск в глубину из вершины $v$. Кратчайшее расстояние от источника до вершины $v$ равно $d$. Предком вершины $v$ при поиске в глубину является $p$.

void dfs(int v, int d, int p = -1)
{

Сохраняем в $dist[v]$ кратчайшее расстояние от источника до вершины $v$.

  dist[v] = d;

Перебираем все ребра $(v,to)$. Для каждого сына $to$ вершины $v$ (где $to$ не является предком $v$) запускаем поиск в глубину. Расстояние от источника до вершины $to$ будет равно $d+1$.

  for (int to : g[v])
    if (to != p) dfs(to, d + 1, v);
}

Основная часть программы. Читаем входные данные.

scanf("%d", &n);
g.resize(n + 1);
dist.resize(n + 1);

Строим неориентированное дерево.

for (i = 1; i < n; i++)
{
  scanf("%d %d", &u, &v);
  g[u].push_back(v);
  g[v].push_back(u);
}

Ищем кратчайшие расстояния от вершины $1$ до всех остальных вершин. Самой удаленной от нее вершиной является $a$.

dfs(1, 0, -1);
a = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Ищем кратчайшие расстояния от вершины $a$ до всех остальных вершин. Самой удаленной от нее вершиной является $b$.

dfs(a, 0,  -1);
b = max_element(dist.begin(), dist.begin() + n + 1) – 
                dist.begin();

Выводим диаметр дерева — кратчайшее расстояние от $a$ до $b$.

printf("%d\n", dist[b]);