14.2 Диаметр дерева

Диаметр дерева — это длина самого длинного простого пути между двумя вершинами дерева. Иначе говоря, мы хотим найти две вершины, которые находятся друг от друга максимально далеко.

Эта идея напрямую следует из раздела книги, где диаметр определяется как максимальная длина пути между двумя узлами дерева, а также приводятся два алгоритма со сложностью O(n) для его поиска: динамика по дереву и подход с двумя обходами. fileciteturn1file0

Что именно считается диаметром

Если путь проходит через k рёбер, то его длина равна k. В олимпиадных задачах почти всегда именно число рёбер и называют длиной пути. Иногда в формулировках вместо этого спрашивают число вершин на пути — тогда ответ будет на 1 больше.

Например, рассмотрим дерево:

1 - 2 - 4 - 7
    |
    5
    |
    6

Один из самых длинных путей здесь — от вершины 6 до вершины 7:

6 -> 5 -> 2 -> 4 -> 7

Он содержит 4 ребра, значит диаметр равен 4.

Важно понимать, что максимальных путей может быть несколько. Нам обычно нужен либо только их длина, либо любые две конечные вершины такого пути.

Главная интуиция

У дерева нет циклов, поэтому путь между двумя вершинами единственный. Это резко упрощает задачу: если мы говорим, что какой-то путь самый длинный, то его нельзя «улучшить» обходом в другую сторону, как это бывает в обычных графах.

Из-за этого у диаметра дерева есть очень удобные свойства:

1. Если смотреть на дерево как на корневое, то у любого пути есть самая верхняя вершина.
2. Концы диаметра всегда лежат в «глубоких» частях дерева.
3. Если стартовать из произвольной вершины и дойти до самой далёкой, то мы попадём в один из концов диаметра.

Именно на этих идеях и строятся оба линейных алгоритма.

---

Алгоритм 1. Динамика по дереву

Книга предлагает сначала мысленно укоренить дерево в любой вершине, а затем для каждой вершины вычислить:

• toLeaf(x) — максимальную длину пути от x вниз до какого-то листа;
• maxLength(x) — максимальную длину пути, у которого вершина x является наивысшей точкой. fileciteturn1file0

Почему этого достаточно

Любой путь в дереве имеет верхнюю вершину, если смотреть на дерево как на корневое. Значит, любой кандидат на диаметр будет полностью учтён в одной из величин maxLength(x).

Тогда общий ответ — это просто максимум по всем вершинам:

diameter = max(maxLength(x))

Как считать toLeaf(x)

Если у вершины x есть дети, то самый длинный путь вниз идёт через того ребёнка, у которого значение toLeaf максимально.

То есть:

toLeaf(x) = 1 + max(toLeaf(child))

Если x — лист, то

toLeaf(x) = 0

потому что от листа до листа вниз идти уже некуда.

Как считать maxLength(x)

Если путь имеет вершину x как наивысшую, то он может:

• либо идти только в один поддеревянный хвост;
• либо проходить через x, соединяя два разных поддерева.

Второй вариант обычно и даёт максимум. Значит, нам нужно взять две наибольшие глубины вниз среди детей вершины x.

Если эти глубины равны best1 и best2, то:

maxLength(x) = best1 + best2

Если детей меньше двух, недостающая глубина считается равной 0.

Почему алгоритм корректен

Пусть самый длинный путь дерева проходит между вершинами u и v. Если дерево укоренено, у этого пути есть наивысшая вершина x.

Тогда путь u -> ... -> x -> ... -> v распадается на две части:

• путь из x вниз в одно поддерево;
• путь из x вниз в другое поддерево, либо вообще пустой путь, если x совпадает с одним из концов.

Чтобы получить максимальный путь с верхней вершиной x, надо взять две самые большие возможные глубины вниз. Значит, maxLength(x) действительно даёт длину лучшего пути с верхней точкой в x.

Так как у любого пути есть верхняя точка, максимум по всем x и есть настоящий диаметр.

Сложность

Если пройти дерево DFS-ом один раз, то каждое ребро мы просмотрим константное число раз. Поэтому:

• время: O(n)
• память: O(n)

Реализация на C++

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

int n;
vector<vector<int>> g;
int diameter = 0;

int dfs(int v, int p) {
    int best1 = 0;
    int best2 = 0;

    for (int to : g[v]) {
        if (to == p) continue;
        int h = dfs(to, v) + 1;

        if (h > best1) {
            best2 = best1;
            best1 = h;
        } else if (h > best2) {
            best2 = h;
        }
    }

    diameter = max(diameter, best1 + best2);
    return best1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.assign(n + 1, {});

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, 0);
    cout << diameter << '\n';
}

Что возвращает этот DFS

Функция dfs(v, p) возвращает длину самого длинного пути от v вниз до листа внутри поддерева v, если не идти обратно в родителя p.

А глобальная переменная diameter во время обхода хранит лучший ответ среди всех вершин.

Небольшой пример

Пусть есть дерево:

1 - 2
    |
    3 - 4 - 5

Если укоренить его в вершине 1, то:

• toLeaf(5) = 0
• toLeaf(4) = 1
• toLeaf(3) = 2
• toLeaf(2) = 3
• toLeaf(1) = 4

Но диаметр здесь не обязательно должен начинаться в корне. Самый длинный путь — 1 -> 2 -> 3 -> 4 -> 5, длина 4. Именно он будет найден как максимум среди значений best1 + best2.

---

Алгоритм 2. Два обхода DFS или BFS

В книге также дан очень элегантный алгоритм:

1. Берём любую вершину a.
2. Находим самую далёкую от неё вершину b.
3. Из b снова запускаем обход и находим самую далёкую вершину c.
4. Расстояние от b до c и есть диаметр дерева. fileciteturn1file0

Почему это работает интуитивно

Если стартовать из произвольной вершины, то самая далёкая вершина обязательно окажется где-то на краю дерева. У дерева «края» — это как раз хорошие кандидаты на концы диаметра.

После первого обхода мы попадаем в один из концов диаметра или в вершину, которая лежит на одном из самых длинных направлений. Если теперь стартовать оттуда, то второй обход неизбежно дойдёт до другого конца диаметра.

Это одна из самых полезных техник по деревьям: она очень проста, легко запоминается и часто применяется прямо в боевых задачах.

Более строгое объяснение

Рассмотрим некоторый настоящий диаметр дерева с концами s и t. Пусть мы стартовали из произвольной вершины a и нашли самую далёкую вершину b.

В дереве расстояния растут вдоль ветвей без неоднозначности. Если бы b не была концом некоторого максимального пути, то можно было бы продолжить путь ещё дальше и получить вершину, которая дальше от a, чем b. Это противоречит выбору b как самой далёкой вершины.

Значит, b — один из крайних кандидатов. Тогда вершина, наиболее удалённая от b, будет другим концом диаметра. Расстояние между ними максимально возможно.

DFS или BFS?

Так как дерево невзвешенное, можно использовать и DFS, и BFS:

• BFS естественно считает расстояния по рёбрам;
• DFS тоже подходит, если аккуратно передавать глубину.

На практике многие пишут именно DFS, если дерево дано списками смежности и ограничение на глубину рекурсии не мешает. Если дерево очень глубокое, безопаснее взять итеративный DFS или BFS.

Реализация на C++ через BFS

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

int n;
vector<vector<int>> g;

pair<int,int> bfs(int start) {
    vector<int> dist(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (dist[to] != -1) continue;
            dist[to] = dist[v] + 1;
            q.push(to);
        }
    }

    int far = start;
    for (int v = 1; v <= n; v++) {
        if (dist[v] > dist[far]) {
            far = v;
        }
    }

    return {far, dist[far]};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.assign(n + 1, {});

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int b = bfs(1).first;
    auto res = bfs(b);

    cout << res.second << '\n';
}

Как восстановить сами концы диаметра

Если нужен не только ответ, но и сам путь, во втором BFS/DFS можно хранить массив parent. Тогда:

• b — первый конец;
• c — второй конец;
• поднимаясь по parent от c к b, мы восстановим весь путь диаметра.

Вот полезная версия с восстановлением пути:

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

int n;
vector<vector<int>> g;

pair<int, vector<int>> bfs_with_parent(int start) {
    vector<int> dist(n + 1, -1), parent(n + 1, -1);
    queue<int> q;
    q.push(start);
    dist[start] = 0;

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int to : g[v]) {
            if (dist[to] != -1) continue;
            dist[to] = dist[v] + 1;
            parent[to] = v;
            q.push(to);
        }
    }

    int far = start;
    for (int v = 1; v <= n; v++) {
        if (dist[v] > dist[far]) far = v;
    }

    return {far, parent};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    g.assign(n + 1, {});

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int b = bfs_with_parent(1).first;
    auto tmp = bfs_with_parent(b);
    int c = tmp.first;
    vector<int> parent = tmp.second;

    vector<int> path;
    for (int v = c; v != -1; v = parent[v]) {
        path.push_back(v);
        if (v == b) break;
    }
    reverse(path.begin(), path.end());

    cout << (int)path.size() - 1 << '\n';
    for (int v : path) cout << v << ' ';
    cout << '\n';
}

---

Сравнение двух подходов

Подход через динамику по дереву

Плюсы:

• очень полезен как шаблон для других DP-задач на деревьях;
• сразу учит смотреть на путь через «наивысшую вершину»;
• легко обобщается на похожие задачи.

Минусы:

• идея сложнее для первого знакомства;
• выше шанс ошибиться в переходах.

Подход через два обхода

Плюсы:

• проще всего запомнить и написать;
• почти всегда это лучший выбор, если нужен только диаметр;
• легко восстановить путь.

Минусы:

• меньше обучает именно динамике по дереву;
• не так напрямую обобщается на более сложные задачи.

Что выбирать на практике

Если в задаче нужно только найти диаметр дерева, обычно выгоднее брать метод с двумя обходами.

Если задача более широкая и рядом всплывают величины вида:

• глубина поддерева,
• лучший путь через вершину,
• лучший ответ по всем поддеревьям,

то удобнее мыслить через DP по дереву.

---

Частые ошибки

1. Путают число рёбер и число вершин

Если путь содержит вершины 1 -> 2 -> 3, то:

• число вершин = 3;
• число рёбер = 2.

Диаметр обычно считается в рёбрах.

2. Забывают, что дерево неориентированное

Если вы храните список смежности, то каждое ребро нужно добавить в обе стороны.

3. В DFS идут назад в родителя

В дереве нет циклов, но если не проверять родителя, рекурсия пойдёт туда-сюда бесконечно.

4. Не учитывают случай из одной вершины

Если n = 1, диаметр равен 0.

5. Пытаются искать диаметр от корня

Диаметр не обязан проходить через выбранный корень. Поэтому идеи вроде «возьму самую глубокую вершину от корня и это ответ» неверны.

---

Минимальный шаблон для запоминания

Если нужен самый короткий боевой шаблон, можно запомнить так:

1. Запусти BFS/DFS из вершины 1, найди самую далёкую b.
2. Запусти BFS/DFS из b, найди самую далёкую c.
3. Расстояние dist(b, c) — это диаметр.

Это один из самых полезных алгоритмов на деревьях, который часто появляется и сам по себе, и как часть более сложных задач.

Итог

Диаметр дерева — это длина самого длинного пути между двумя вершинами. Книга показывает два решения за O(n): динамику по дереву через значения toLeaf и maxLength, а также метод двух обходов, где сначала ищется далёкая вершина от произвольной точки, а затем далёкая вершина от неё. fileciteturn1file0

Для практики в соревнованиях метод двух обходов обычно самый удобный. Но для глубокого понимания деревьев особенно полезно освоить и DP-подход, потому что он лежит в основе многих следующих задач на деревья.