Центроидная декомпозиция: разделяй и властвуй на дереве

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

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

Дерево из трёх тысяч вершин. Сколько пар вершин находится на расстоянии ровно 7? Прямой путь - обход в ширину из каждой вершины, n обходов, O(n²).

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

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

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

Механизм: центроид, пути через него, рекурсия

ЦЕНТРОИД компоненты из m вершин:
    посчитать размеры поддеревьев от любой вершины;
    центроид - вершина, у которой все части (сыновья и «вверх»,
    m − размер) не больше m/2
    существует: начни с корня и иди в сына с частью > m/2, пока такой
    есть; сверху от пройденной вершины всегда < m/2

ДЕКОМПОЗИЦИЯ:
    c = центроид компоненты
    учесть все пути через c
    удалить c; повторить в каждой оставшейся компоненте

ПУТИ ЧЕРЕЗ c ДЛИНЫ K:
    счётчик[d] - сколько вершин на расстоянии d от c в уже
    просмотренных ветках (счётчик[0] = 1 - сам c)
    для каждой ветки: собрать её расстояния; для каждого d
    прибавить счётчик[K − d]; ПОТОМ добавить расстояния ветки в счётчик

Почему ветку добавляют в счётчик только после подсчёта. Две вершины ОДНОЙ ветки соединены путём, не проходящим через c: если сложить их расстояния до c, получится длина несуществующего пути с заходом в c и обратно. Такие пары посчитаются позже, на нижних уровнях, где эта ветка - отдельная компонента.

Почему O(n · log n). После удаления центроида каждая часть не больше половины, значит, у вершины не больше log₂ n уровней, на которых она лежит в обрабатываемой компоненте. На каждом уровне все компоненты вместе содержат не больше n вершин, и каждая обрабатывается за время, линейное в её размере.

Правило

Центроид - вершина, после удаления которой все части не больше половины; он есть в любом дереве и находится одним проходом по размерам поддеревьев. Центроидная декомпозиция обрабатывает пути через центроид, удаляет его и рекурсивно повторяет в частях: уровней не больше log₂ n, работы на уровне - O(n). Пути через центроид собирают по веткам и ветку добавляют в общий счётчик только после подсчёта её пар - чтобы не склеить две вершины одной ветки.

Разбор: путь из семи вершин, пары на расстоянии 2

1 – 2 – 3 – 4 – 5 – 6 – 7

уровень 1: центроид 4 (части {1 2 3} и {5 6 7} - по 3 ≤ 7/2)
    счётчик[0] = 1
    ветка 3: расстояния 3:1  2:2  1:3
        d = 2 → счётчик[0] = 1 → пара (4, 2)
        счётчик: [1, 1, 1, 1]
    ветка 5: расстояния 5:1  6:2  7:3
        d = 1 → счётчик[1] = 1 → пара (3, 5)
        d = 2 → счётчик[0] = 1 → пара (4, 6)
    через 4: 3 пары

уровень 2: {1 2 3} - центроид 2, пара (1, 3)
           {5 6 7} - центроид 6, пара (5, 7)
уровень 3: одиночные вершины, пар нет

всего 5 пар: (1,3) (2,4) (3,5) (4,6) (5,7) - верно

Уровней три: 7 → 3 → 1. Пара (1, 3) не посчиталась на первом уровне, потому что обе вершины в одной ветке, - её нашёл второй уровень.

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

Программа строит дерево, считает пары на расстоянии K = 7 центроидной декомпозицией и сверяет с перебором - обходом в ширину из каждой вершины.

import math
import random
from collections import deque

rng = random.Random(13)
n, K = 3000, 7
sosedi = [[] for _ in range(n)]
for v in range(1, n):
    p = rng.randrange(max(0, v - 20), v)
    sosedi[v].append(p)
    sosedi[p].append(v)
udalena = [False] * n
rabota = 0


def komponenta(s):                    # вершины компоненты и их отцы
    global rabota
    poryadok, otec = [s], {s: -1}
    for v in poryadok:
        rabota += 1
        for u in sosedi[v]:
            if not udalena[u] and u != otec[v]:
                otec[u] = v
                poryadok.append(u)
    return poryadok, otec


def centroid(s):                      # все части после удаления ≤ m/2
    poryadok, otec = komponenta(s)
    m, razmer = len(poryadok), {}
    for v in reversed(poryadok):
        razmer[v] = 1 + sum(razmer[u] for u in sosedi[v]
                            if not udalena[u] and u != otec[v])
    for v in poryadok:
        chasti = [razmer[u] for u in sosedi[v]
                  if not udalena[u] and u != otec[v]] + [m - razmer[v]]
        if max(chasti) <= m // 2:
            return v


def par_cherez(c):                    # пары на расстоянии K через c
    sch = [0] * (K + 1)
    sch[0] = 1                        # сам центроид
    pary = 0
    for u in sosedi[c]:
        if udalena[u]:
            continue
        rasst = []
        och = deque([(u, c, 1)])
        while och:                    # расстояния в одной ветке
            v, ot, d = och.popleft()
            if d > K:
                continue
            rasst.append(d)
            for w in sosedi[v]:
                if w != ot and not udalena[w]:
                    och.append((w, v, d + 1))
        pary += sum(sch[K - d] for d in rasst)
        for d in rasst:               # ветку добавляем после подсчёта
            sch[d] += 1
    return pary


vsego, glubina, stek = 0, 0, [(0, 1)]
while stek:
    s, ur = stek.pop()
    c = centroid(s)
    vsego += par_cherez(c)
    udalena[c] = True
    glubina = max(glubina, ur)
    stek.extend((u, ur + 1) for u in sosedi[c] if not udalena[u])


def bfs(s):
    d = [-1] * n
    d[s], och = 0, 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


perebor = sum(bfs(s).count(K) for s in range(n)) // 2
print("пар на расстоянии", K, ":", vsego, " перебор:", perebor)
print("уровней центроидов:", glubina, " log2 n =",
      round(math.log2(n), 1))
print("работа построения:", rabota, " n·log2 n =",
      round(n * math.log2(n)))

пар на расстоянии 7 : 10883  перебор: 10883
уровней центроидов: 12  log2 n = 11.6
работа построения: 26322  n·log2 n = 34652

Ответ совпал с перебором. Уровней 12 - ровно ⌊log₂ 3000⌋ + 1, как и обещает удвоение. Работа построения декомпозиции (сколько раз вершины проходились при поиске центроидов) - 26 тысяч, меньше n · log₂ n; перебор же делает три тысячи обходов по три тысячи вершин - девять миллионов шагов.

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

Первая ошибка - делить по корню или по произвольной вершине: на дереве-цепочке «части» почти равны целому, уровней становится n, и всё снова O(n²). Вторая - добавить ветку в счётчик до подсчёта её пар: появятся «пути» между вершинами одной ветки через центроид, которых нет, и ответ завысится. Третья - забыть, что при поиске центроида части считаются с учётом уже удалённых вершин: размеры надо пересчитывать в текущей компоненте, а не брать из исходного дерева. Четвёртая - собирать расстояния ветки без отсечки по K: работа на уровне останется линейной, но на больших деревьях лишние обходы заметны.

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

Задачи «посчитать или найти все пути с условием» в деревьях: пары узлов сети на заданном расстоянии, пути с суммой весов не больше порога, ближайший «отмеченный» узел для каждого запроса с изменениями (центроидное дерево хранит ответы на log n уровнях). Само понятие центроида - это «центр масс» дерева: точка, удаление которой разбивает систему на сбалансированные куски. Так выбирают корень иерархии для балансировки, точку для размещения общего ресурса и место разреза в распределённых алгоритмах на деревьях.

Теперь сам

Звезда: центр 0 и листья 1..9. Где центроид, сколько уровней декомпозиции и сколько пар на расстоянии 2 найдёт первый уровень?