За допомогою двох запусків пошуку в глибину знайдемо діаметр дерева.

Оскільки дерево — це зв’язний граф без циклів, як пошук в глибину (DFS), так і пошук в ширину (BFS) коректно знаходять найкоротші відстані від стартової вершини до всіх інших.

Позначимо через $a$ і $b$ дві вершини, що знаходяться на максимальній відстані одна від одної — тобто утворюють діаметр дерева.

Визначимо найкоротші відстані від вершини $a$ до всіх інших і збережемо їх в масиві $dista$, а від вершини $b$ — у масиві $distb$.

Тоді для кожної вершини i найбільша відстань до іншої вершини буде дорівнювати

Приклад

Розгляньмо дерево з прикладу.

Діаметром дерева може бути, наприклад, шлях між вершинами $2$ і $5$.

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

Вхідне дерево зберігається у вигляді списку суміжності $g$.

Найкоротші відстані від вершин $a$ та $b$ зберігаються в масивах $dista$ і $distb$.

vector<vector<int>> g;
vector<int> dista, distb;

Функція dfs виконує пошук в глибину з вершини $v$.

• Параметр $d$ позначає найкоротшу відстань від джерела до вершини $v$.

• Результати зберігаються в масиві $dist$.

• Параметр $p$ вказує на предка вершини $v$ в процесі обходу.

void dfs(int v, int d, vector<int>& dist, int p = -1)
{

Записуємо в dist[v] найкоротшу відстань від джерела до вершини $v$.

  dist[v] = d;

Перебираємо всі ребра (v, to). Для кожного сина $to$ вершини $v$ (вершина $to$ не є предком вершини $v$) запускаємо пошук в глибину.

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

Основна частина програми. Читаємо вхідні дані.

scanf("%d", &n);
g.resize(n + 1);
dista.resize(n + 1);
distb.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, dista, -1);
a = max_element(dista.begin() + 1, dista.begin() + n + 1) - dista.begin();

Потім обчислюємо найкоротші відстані від вершини $a$ і зберігаємо їх в масиві $dista$. Найвіддаленішою вершиною від $a$ виявляється вершина $b$. Відстань між вершинами $a$ і $b$ є діаметром дерева.

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

Обчислюємо найкоротші відстані від вершини $b$ і зберігаємо їх в масиві $distb$.

dfs(b, 0, distb, -1);

Для кожної вершини $i$ виводимо відстань до найвіддаленішої від неї вершини.

for (i = 1; i <= n; i++)
  printf("%d ", max(dista[i], distb[i]));
printf("\n");

Python реалізація

Збільшимо стек для рекурсії.

import sys
sys.setrecursionlimit(1000000)

Функція dfs виконує пошук в глибину з вершини $v$.

• Параметр $d$ позначає найкоротшу відстань від джерела до вершини $v$.

• Результати зберігаються в масиві $dist$.

• Параметр $p$ вказує на предка вершини $v$ в процесі обходу.

def dfs(v, d, dist, p =- 1):

Записуємо в dist[v] найкоротшу відстань від джерела до вершини $v$.

  dist[v] = d

Перебираємо всі ребра (v, to). Для кожного сина $to$ вершини $v$ (вершина $to$ не є предком вершини $v$) запускаємо пошук в глибину.

  for to in g[v]:
    if to != p:
      dfs(to, d + 1, dist, v)

Основна частина програми. Читаємо вхідні дані.

n = int(input())
g = [[] for _ in range(n + 1)]
dista = [0] * (n + 1)
distb = [0] * (n + 1)

Будуємо неорієнтоване дерево.

for _ in range(n - 1):
  u, v = map(int, input().split())
  g[u].append(v)
  g[v].append(u)

Знаходимо найкоротші відстані від вершини $1$. Найвіддаленішою від неї вершиною є вершина $a$.

dfs(1, 0, dista)
a = dista.index(max(dista[1:]))

Потім обчислюємо найкоротші відстані від вершини $a$ і зберігаємо їх в масиві $dista$. Найвіддаленішою вершиною від $a$ виявляється вершина $b$. Відстань між вершинами $a$ і $b$ є діаметром дерева.

dfs(a, 0, dista)
b = dista.index(max(dista[1:]))

Обчислюємо найкоротші відстані від вершини $b$ і зберігаємо їх в масиві $distb$.

dfs(b, 0, distb)

Для кожної вершини $i$ виводимо відстань до найвіддаленішої від неї вершини.

result = [max(dista[i], distb[i]) for i in range(1, n + 1)]
print(*result)