14.3 Все самые длинные пути¶

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

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

Что именно требуется найти¶

Пусть maxLength(x) — максимальная длина пути, который начинается в вершине x.

Длина пути здесь — это число рёбер.

Рассмотрим дерево:

graph TD
    v1[1] --- v2[2]
    v1 --- v3[3]
    v1 --- v4[4]
    v2 --- v5[5]
    v2 --- v6[6]

Hold "Ctrl" to enable pan & zoom

Для него ответы такие:

maxLength(1) = 2
maxLength(2) = 2
maxLength(3) = 3
maxLength(4) = 3
maxLength(5) = 3
maxLength(6) = 3

Например, из вершины 4 самый длинный путь — 4 -> 1 -> 2 -> 6, его длина равна 3.

Главная идея¶

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

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

Именно из-за второго случая задача чуть сложнее обычного ДП по дереву.

Поэтому удобно разбить решение на две части:

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

Шаг 1. Самый длинный путь вниз¶

Выберем произвольный корень, например вершину 1.

Тогда для каждой вершины x определим:

down[x] — длина самого длинного пути, который начинается в x и идёт только вниз, в её поддерево.

Если x — лист, то down[x] = 0, потому что вниз идти некуда.

Если у x есть дети, то:

down[x] = 1 + max(down[child])

где максимум берётся по всем детям вершины x.

Интуиция¶

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

Пример¶

Для дерева выше:

down[5] = 0
down[6] = 0
down[3] = 0
down[4] = 0
down[2] = 1
down[1] = 2

Например:

из 2 можно пойти в 5 или 6, поэтому down[2] = 1
из 1 лучший спуск идёт через 2, поэтому down[1] = 2

Почему одного массива `down` недостаточно¶

Посмотрим на вершину 3.

Если учитывать только путь вниз, то down[3] = 0, ведь у неё нет детей.

Но настоящий ответ — 3, потому что путь может идти так:

3 -> 1 -> 2 -> 5

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

Значит, нам нужно уметь считать не только путь вниз, но и лучший путь в сторону родителя.

Шаг 2. Путь через родителя¶

Обозначим:

up[x] — длина самого длинного пути, который начинается в вершине x и первым шагом идёт к её родителю.

Тогда окончательный ответ:

maxLength(x) = max(down[x], up[x])

Для корня up[root] = 0, потому что у него нет родителя.

Теперь разберёмся, как считать up[x].

Пусть p — родитель вершины x. Когда мы поднимаемся из x в p, дальше у нас есть два варианта:

идти ещё выше, используя путь up[p]
уйти из p в другое поддерево, не через x

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

Два лучших значения для каждой вершины¶

Для каждой вершины x будем хранить:

best1[x] — длина самого длинного пути из x
best2[x] — длина второго по длине пути из x, причём он идёт в другом направлении

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

Это нужно, потому что при переходе из родителя p в ребёнка x нельзя снова использовать ветку x. Если лучший путь у p как раз шёл через x, то ребёнку нужно дать второй лучший вариант.

Как пересчитывать ответ для ребёнка¶

Пусть мы находимся в вершине p и хотим посчитать up[x] для её ребёнка x.

Есть два случая:

Случай 1. Лучший путь из `p` не идёт через `x`¶

Тогда ребёнок может подняться в p, а дальше пойти по лучшему пути из p.

Получаем:

up[x] = 1 + best1[p]

Случай 2. Лучший путь из `p` идёт через `x`¶

Тогда использовать best1[p] нельзя, иначе мы вернёмся в то же поддерево. Нужно взять второй лучший вариант:

up[x] = 1 + best2[p]

Именно поэтому хранение двух максимумов полностью решает задачу.

Общая схема решения¶

Первый DFS¶

Обходим дерево снизу вверх и считаем:

down[x]
какой ребёнок даёт лучший спуск
best1[x] и best2[x]

Второй DFS¶

Обходим дерево сверху вниз и считаем:

up[x]
затем итоговый ответ ans[x] = max(down[x], up[x])

Итоговая сложность:

по времени: O(n)
по памяти: O(n)

Потому что каждое ребро обрабатывается константное число раз.

Подробный пример¶

Возьмём дерево:

graph TD
    v1[1] --- v2[2]
    v1 --- v3[3]
    v1 --- v4[4]
    v2 --- v5[5]
    v2 --- v6[6]

Hold "Ctrl" to enable pan & zoom

После первого обхода¶

down[5] = 0
down[6] = 0
down[3] = 0
down[4] = 0
down[2] = 1
down[1] = 2

Для вершины 1:

лучший путь идёт через 2 и имеет длину 2
второй лучший путь идёт через 3 или 4 и имеет длину 1

То есть:

best1[1] = 2
best2[1] = 1

Для вершины 2:

best1[2] = 1
best2[2] = 1

После второго обхода¶

up[1] = 0
для вершины 2: лучший путь у 1 идёт через 2, значит берём второй максимум: up[2] = 1 + best2[1] = 2
для вершины 3: лучший путь у 1 не идёт через 3, значит up[3] = 1 + best1[1] = 3
аналогично up[4] = 3
для вершины 5: лучший путь у 2 идёт через 5 или 6, поэтому берём допустимый альтернативный маршрут и получаем up[5] = 3
аналогично up[6] = 3

Итог:

ans[1] = 2
ans[2] = 2
ans[3] = 3
ans[4] = 3
ans[5] = 3
ans[6] = 3

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

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

const int N = 200005;

vector<int> g[N];
int downLen[N];
int upLen[N];
int ans[N];
int bestChild[N];
int best1[N], best2[N];

void dfs1(int v, int p) {
    best1[v] = 0;
    best2[v] = 0;
    bestChild[v] = -1;

    for (int to : g[v]) {
        if (to == p) continue;
        dfs1(to, v);

        int cur = downLen[to] + 1;
        if (cur > best1[v]) {
            best2[v] = best1[v];
            best1[v] = cur;
            bestChild[v] = to;
        } else if (cur > best2[v]) {
            best2[v] = cur;
        }
    }

    downLen[v] = best1[v];
}

void dfs2(int v, int p) {
    ans[v] = max(downLen[v], upLen[v]);

    for (int to : g[v]) {
        if (to == p) continue;

        int use = best1[v];
        if (bestChild[v] == to) {
            use = best2[v];
        }

        upLen[to] = max(upLen[v] + 1, use + 1);
        dfs2(to, v);
    }
}

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

    int n;
    cin >> n;

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

    dfs1(1, 0);
    upLen[1] = 0;
    dfs2(1, 0);

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " \n"[i == n];
    }

    return 0;
}

Как работает эта реализация¶

Массив `downLen`¶

downLen[v] — лучший путь вниз из вершины v.

Массивы `best1` и `best2`¶

best1[v] — лучший маршрут из v через одного из её детей
best2[v] — второй лучший маршрут

Массив `bestChild`¶

Запоминает, через какого ребёнка достигается best1[v]. Это нужно, чтобы при переходе в ребёнка не использовать ту же ветку повторно.

Массив `upLen`¶

upLen[v] — лучший путь из v, который сначала идёт к родителю.

Когда мы переходим из v в to, то у to есть два кандидата:

подняться выше через upLen[v]
использовать другую ветку из v

Поэтому:

upLen[to] = max(upLen[v] + 1, use + 1)

где use — либо best1[v], либо best2[v].

Более короткая формулировка идеи¶

Эту задачу можно запомнить так:

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

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

1. Хранить только один максимум¶

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

2. Забыть, что длина считается в рёбрах¶

У листа ответ равен 0, а не 1.

3. Перепутать `down` и итоговый ответ¶

down[x] — это только путь вниз. Настоящий ответ может идти через родителя.

4. Использовать слишком медленное решение¶

Если из каждой вершины отдельно запускать BFS/DFS, получится O(n^2), что слишком медленно для больших деревьев.

Альтернативный взгляд через диаметр¶

Есть ещё полезный факт: для любой вершины её ответ равен расстоянию до одного из концов диаметра.

То есть можно:

найти один конец диаметра A
найти другой конец диаметра B
посчитать расстояния от A до всех вершин
посчитать расстояния от B до всех вершин
для каждой вершины взять

ans[x] = max(distA[x], distB[x])

Это тоже работает за O(n) и часто даже проще в реализации.

Но подход с down/up и двумя максимумами очень полезен методически, потому что он учит делать более общее ДП по дереву.

Ещё один пример¶

Рассмотрим цепочку:

graph LR
    v1[1] --- v2[2] --- v3[3] --- v4[4] --- v5[5]

Hold "Ctrl" to enable pan & zoom

Тогда ответы будут:

для 1 — 4
для 2 — 3
для 3 — 2
для 4 — 3
для 5 — 4

То есть:

4 3 2 3 4

Здесь хорошо видно, что вершины у концов цепочки имеют наибольший ответ, а центральная вершина — меньший.

Вывод¶

Задача «все самые длинные пути» учит важному приёму в деревьях:

недостаточно уметь считать ответ только внутри поддерева;
часто нужно дополнительно передавать информацию сверху вниз;
для корректного пересчёта нередко требуется хранить два лучших значения, а не одно.

14.3 Все самые длинные пути¶

Что именно требуется найти¶

Главная идея¶

Шаг 1. Самый длинный путь вниз¶

Интуиция¶

Пример¶

Почему одного массива down недостаточно¶

Шаг 2. Путь через родителя¶

Два лучших значения для каждой вершины¶

Как пересчитывать ответ для ребёнка¶

Случай 1. Лучший путь из p не идёт через x¶

Случай 2. Лучший путь из p идёт через x¶

Общая схема решения¶

Первый DFS¶

Второй DFS¶

Подробный пример¶

После первого обхода¶

После второго обхода¶

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

Как работает эта реализация¶

Массив downLen¶

Массивы best1 и best2¶

Массив bestChild¶

Массив upLen¶

Более короткая формулировка идеи¶

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

1. Хранить только один максимум¶

2. Забыть, что длина считается в рёбрах¶

3. Перепутать down и итоговый ответ¶

4. Использовать слишком медленное решение¶

Альтернативный взгляд через диаметр¶

Ещё один пример¶

Вывод¶

Почему одного массива `down` недостаточно¶

Случай 1. Лучший путь из `p` не идёт через `x`¶

Случай 2. Лучший путь из `p` идёт через `x`¶

Массив `downLen`¶

Массивы `best1` и `best2`¶

Массив `bestChild`¶

Массив `upLen`¶

3. Перепутать `down` и итоговый ответ¶