Диаметр дерева и перекоренение: ответ для каждой вершины за два прохода

Если ты знаешь, почему диаметр дерева ищется двумя обходами, и умеешь переносить ответ с отца на сына формулой перекоренения, листай до «Теперь сам».

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

Сеть магазинов связана дорогами без циклов - это дерево из двух тысяч точек. Два вопроса логиста: какие две точки дальше всего друг от друга (на сколько переходов рассчитывать худшую доставку) и в какой точке ставить склад, чтобы СУММА расстояний до всех магазинов была наименьшей.

Наивно оба вопроса требуют знать расстояния между всеми парами: обход в ширину из каждой из n вершин, n² работы. Прежде чем читать дальше, попробуй угадать: сколько обходов на самом деле хватит для первого вопроса? А для второго?

На что это похоже

Найти двух самых далёких друг от друга людей в длинной извилистой очереди с ответвлениями. Можно мерить расстояние между каждой парой. А можно встать в любом месте, найти, кто дальше всех от тебя, пойти к нему - и уже от него найти самого дальнего. Самый дальний от случайной точки обязательно стоит на одном из концов самой длинной цепочки.

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

Механизм: два обхода и перенос корня

ДИАМЕТР
1. обход от любой вершины a → самая дальняя b
2. обход от b → самая дальняя c
   dist(b, c) - диаметр

ПЕРЕКОРЕНЕНИЕ для S(v) = сумма расстояний от v до всех вершин
проход вниз от корня r:  глубины, S(r) = сумма глубин
проход вверх:            размер поддерева size(v) для корня r
проход вниз:             S(v) = S(отец v) − size(v) + (n − size(v))
                         size(v) вершин стали ближе на 1,
                         n − size(v) вершин - дальше на 1

Почему первый обход приводит к концу диаметра. Пусть диаметр - путь x–y, а b - самая дальняя от a. Путь от a до b в дереве обязательно пересекается с путём x–y или подходит к нему по единственной дороге; если бы b не была концом какого-то самого длинного пути, то от точки встречи с x–y до x или до y было бы дальше, чем до b, - и b не была бы самой дальней от a. Значит, от b до самой дальней вершины - как раз диаметр. Работает только в ДЕРЕВЕ (и с неотрицательными длинами рёбер): в графе с циклами утверждение ложно.

Правило

Диаметр дерева - два обхода: от любой вершины к самой дальней b, от b к самой дальней c; dist(b, c) - ответ. Ответы «для каждой вершины как корня» считают перекоренением: посчитать ответ для одного корня и размеры поддеревьев, затем пройти сверху вниз и получать ответ сына из ответа отца поправкой за ребро. Для суммы расстояний поправка - − size(v) + (n − size(v)). Всё - O(n) вместо n обходов за O(n²).

Разбор: шесть вершин

рёбра: 1–2, 2–3, 2–4, 4–5, 5–6

            1
            |
            2
           / \
          3   4
              |
              5
              |
              6

ДИАМЕТР
обход от 3: расстояния 2:1  1:2  4:2  5:3  6:4  →  b = 6
обход от 6: 5:1  4:2  2:3  1:4  3:4      →  диаметр 4 (до 1 или 3)

ПЕРЕКОРЕНЕНИЕ, корень 1
глубины: 1:0  2:1  3:2  4:2  5:3  6:4    S(1) = 12
размеры: 2:5  3:1  4:3  5:2  6:1
S(2) = S(1) − 5 + (6 − 5) = 12 − 5 + 1 =  8
S(3) = S(2) − 1 + 5       =  8 − 1 + 5 = 12
S(4) = S(2) − 3 + 3       =  8
S(5) = S(4) − 2 + 4       = 10
S(6) = S(5) − 1 + 5       = 14

Склад ставить в вершину 2 или 4 - сумма 8. Проверка напрямую для 4: до 2, 5 по одному, до 1, 3, 6 по два - 1 + 1 + 2 + 2 + 2 = 8. Каждый ответ получен из соседнего за одно действие.

Разбор: дерево на две тысячи вершин

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

import random
from collections import deque

rng = random.Random(6)
n = 2000
sosedi = [[] for _ in range(n)]
for v in range(1, n):                 # случайное дерево
    p = rng.randrange(v)
    sosedi[v].append(p)
    sosedi[p].append(v)


def rasstoyaniya(s):                  # обход в ширину от s
    d = [-1] * n
    d[s] = 0
    och = deque([s])
    while och:
        v = och.popleft()
        for u in sosedi[v]:
            if d[u] < 0:
                d[u] = d[v] + 1
                och.append(u)
    return d


# диаметр: два обхода
d0 = rasstoyaniya(0)
b = d0.index(max(d0))                 # самая дальняя от произвольной
db = rasstoyaniya(b)
print("диаметр двумя обходами:", max(db))

# сумма расстояний от каждой вершины: перекоренение
poryadok, otec = [0], [-1] * n        # порядок обхода от корня 0
for v in poryadok:
    for u in sosedi[v]:
        if u != otec[v]:
            otec[u] = v
            poryadok.append(u)
razmer = [1] * n
for v in reversed(poryadok):          # снизу вверх: размеры поддеревьев
    if otec[v] >= 0:
        razmer[otec[v]] += razmer[v]
summa = [0] * n
summa[0] = sum(d0)                    # ответ для корня - один обход
for v in poryadok[1:]:                # сверху вниз: сдвиг корня на ребро
    summa[v] = summa[otec[v]] - razmer[v] + (n - razmer[v])

vse = [rasstoyaniya(s) for s in range(n)]     # перебор: n обходов
assert max(map(max, vse)) == max(db)
assert summa == [sum(d) for d in vse]
centr = summa.index(min(summa))
print("перебор подтвердил: диаметр", max(map(max, vse)),
      "и все", n, "сумм расстояний")
print("лучшее место для склада: вершина", centr, "сумма", summa[centr])

диаметр двумя обходами: 32
перебор подтвердил: диаметр 32 и все 2000 сумм расстояний
лучшее место для склада: вершина 1 сумма 14528

Два обхода дали тот же диаметр, что и две тысячи; перекоренение - те же две тысячи сумм, что и перебор, но за три прохода по дереву вместо двух тысяч обходов. На дереве в миллион вершин разница - это секунда против недели.

Что ломается без этого

Первая ошибка - перенести «два обхода» на граф с циклами: там первый обход может прийти не к концу самого длинного кратчайшего пути, и ответ окажется меньше настоящего: на графах два обхода дают лишь оценку снизу. Вторая - отрицательные длины рёбер: доказательство опиралось на то, что удлинение пути не уменьшает расстояние. Третья - в перекоренении перепутать стороны: size(v) - это поддерево СЫНА относительно исходного корня, оно приближается; если взять размер «со стороны отца», знак поправки обернётся и все ответы, кроме корня, будут неверны. Четвёртая - рекурсивный обход на дереве-цепочке в сто тысяч вершин: глубина рекурсии упрётся в предел Python; поэтому в программе порядок обхода строится списком.

Зачем это в работе

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

Теперь сам

Дерево - звезда: центр 0, листья 1..5. Чему равен диаметр, какие S(v) у центра и у листа? Получи S(лист) из S(центр) формулой перекоренения.