Діаметр дерева (Розбір)

Діаметр дерева — це довжина найдовшого шляху в дереві. Іншими словами, потрібно знайти дві вершини $a$ та $b$ такі, що відстань між ними максимальна.

Для розв'язання цієї задачі скористаємося таким алгоритмом:

• Спочатку виконаємо обхід у глибину, починаючи з будь-якої вершини дерева, наприклад, вершини $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)
{

Збережемо найкоротшу відстань від джерела до вершини $v$ у dist[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();

Знайдемо найкоротші відстані від вершини $b$ до всіх інших вершин. Найвіддаленіша від неї вершина — це $b$.

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

Виведемо діаметр дерева — найкоротшу відстань від $a$ до $b$.

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