Центроидная декомпозиция
Также: Centroid decomposition · центроид дерева · centroid of a tree · дерево центроидов · centroid tree · разделяй и властвуй на дереве · ближайшая отмеченная вершина
Как отвечать на вопросы о расстояниях в дереве, которое не меняется, когда меняются отметки на нём. Берём центроид — вершину, после удаления которой все части не больше половины, — и повторяем в частях. Уровней не больше log₂ n, а любой путь проходит через центроид какого-то уровня.
В каталоге Glottolog 7567 языков, которые разложены по семьям по родству, и большая грамматика — больше трёхсот страниц — есть у 1937 из них. Если язык описан плохо, одна из первых опор полевого лингвиста — ближайший описанный родственник: его грамматика подсказывает, чего ждать. Ниже дерево одной языковой семьи из Glottolog: языки на окружности, подгруппы внутри. Нажмите на язык без грамматики, и сцена покажет ближайшего описанного родственника. А если включить отметки, нажатие «выпустит» новую грамматику, и станет видно, кому она помогла.
У нижнечулымского языка есть только набросок грамматики, и ближайший тюркский язык с большой — древнетюркский, в четырёх шагах по дереву. Переключитесь на трансновогвинейскую семью: там из 307 языков большая грамматика у 27, и у языка Uya ближайший описанный родственник в семи шагах. Отметьте его соседа Ogea — у Ogea сейчас только набросок, — и до описанного языка станет ближе 26 языкам сразу.
Для одного вопроса хватило бы обхода в ширину от языка до первого отмеченного. Для всех языков сразу — одного обхода из всех отмеченных. Трудность в том, что отметки появляются по одной, а вопросы идут вперемешку с ними. Обход на каждый вопрос стоит O(n). Центроидная декомпозиция отвечает за O(log n) и так же быстро принимает новую отметку.
Идея
Центроид дерева — вершина, после удаления которой каждая из оставшихся частей не больше половины дерева. Возьмём центроид, запомним расстояния от него до всех вершин, удалим его и сделаем то же в каждой части. Центроид части назовём центроидом следующего уровня. Получится дерево центроидов: каждая вершина рано или поздно сама становится центроидом, и над ней стоят центроиды всех кусков, в которых она лежала.
Каждая вершина помнит расстояния до своих центроидов — их не больше log₂ n + 1. Каждый центроид помнит ближайшую отмеченную вершину в своём куске. Отметить вершину — обновить её центроиды; спросить — взять наименьшее «расстояние до центроида плюс его ближайшая отмеченная».
Вот как делится тюркская семья. Сначала центроид всей семьи, потом по центроиду в каждом оставшемся куске, и так до одиночных вершин. В конце — вопрос о нижнечулымском: обходим только его центроиды.
Почему это работает
В любом дереве из n вершин есть вершина, после удаления которой каждая часть содержит не больше n/2 вершин.
Подвесим дерево за любую вершину и посчитаем размеры поддеревьев. Начнём с корня. Пока у текущей вершины c есть ребёнок с поддеревом больше n/2, переходим в него. Размеры поддеревьев при этом строго уменьшаются, так что спуск кончится. В остановившейся вершине все поддеревья детей не больше n/2. Остаётся часть «над» c: в ней n − size(c) вершин. В корне её нет, а в любую другую вершину мы пришли потому, что size(c) > n/2, значит, над ней меньше n/2.
Дерево центроидов имеет не больше ⌊log₂ n⌋ + 1 уровней, а каждая вершина хранит не больше ⌊log₂ n⌋ + 1 расстояний.
Кусок уровня k — часть, оставшаяся после удаления центроида куска уровня k − 1, поэтому в нём не больше половины вершин того куска, а по индукции — не больше n/2k. В непустом куске хотя бы одна вершина, значит, 2k ≤ n и k ≤ log₂ n. Вершина лежит ровно в одном куске каждого уровня, пока сама не станет центроидом, и хранит по расстоянию на уровень.
Для любой вершины v расстояние до ближайшей отмеченной вершины равно наименьшему из чисел dist(v, c) + best(c) по всем центроидам c, над v, где best(c) — расстояние от c до ближайшей отмеченной вершины его куска.
Каждое такое число — длина какого-то маршрута от v через c к отмеченной вершине, поэтому оно не меньше настоящего расстояния. Обратно, пусть m — ближайшая к v отмеченная вершина. Пока ни одна вершина пути от v до m не взята центроидом, весь путь лежит в одном куске: удалённые вершины его не задевали. Возьмём первый центроид c, оказавшийся на этом пути. Перед этим и v, и m лежали в куске c, поэтому c — один из центроидов над v, а best(c) ≤ dist(c, m). Так как c лежит на пути, dist(v, c) + dist(c, m) = dist(v, m), и наименьшее из чисел не больше настоящего расстояния.
Отметка вершины u обновляет best у её центроидов — не больше log₂ n + 1 чисел, вопрос перебирает столько же. Подготовка — O(n log n): на каждом уровне обходы кусков в сумме проходят каждую вершину не больше раза.
Код
Куски обрабатываются уровень за уровнем без рекурсии. Для каждого куска — обход, размеры поддеревьев, спуск к центроиду, как в доказательстве, и обход в ширину от центроида: он записывает каждой вершине куска пару «центроид, расстояние». Отметки — языки с большой грамматикой; все ответы сверяются с обходом в ширину сразу из всех отмеченных.
В дереве 12 208 вершин — семьи, подгруппы, языки, — а уровней центроидов 11: столько же, сколько у самой большой семьи, атлантико-конголезской, в которой больше двух тысяч вершин. В среднем вершина хранит 5 пар. У 1323 языков без большой грамматики описан ближайший сосед по подгруппе — два шага, а у 445 описанных родственников в семье нет вовсе: 138 из них — изоляты, языки без известной родни.
Сколько это стоит
| Способ | Подготовка | Отметка | Вопрос |
|---|---|---|---|
| Обход в ширину от вопроса до первой отметки | — | O(1) | до O(n) |
| Обход из всех отмеченных после каждой отметки | — | O(n) | O(1) |
| Центроидная декомпозиция | O(n log n) | O(log n) | O(log n) |
Замер на случайных деревьях: каждое десятое из 600 действий — новая отметка, остальные — вопросы, первая отметка ставится сразу. Меряются только действия, подготовка у центроидов — отдельно, O(n log n).
На 32 000 вершинах обход от вопроса медленнее центроидов больше чем в сто раз на Python и в двести с лишним раз на Go: отметок мало, и обходу приходится просматривать большую часть дерева, пока не найдётся хоть одна. Центроиды почти не замечают роста дерева — вершина хранит логарифм пар.
Где легко ошибиться
- Размеры старого куска. Размеры поддеревьев пересчитывают в каждом куске заново: после удаления центроида куски меньше, и прежние размеры к ним не относятся.
- Центроид — не середина диаметра. Центр дерева — середина самого длинного пути — делит дерево по длине, а не по числу вершин. У метлы — длинной ручки с пучком листьев на конце — центр приходится на середину ручки, а после его удаления пучок и полручки остаются в одной части: больше половины дерева.
- Дерево центроидов — не подграф. Родитель центроида в нём может быть далеко от него в исходном дереве; расстояния надо брать из записанных пар, а не считать по рёбрам дерева центроидов.
- Удаление отметок. Число best(c) умеет только уменьшаться. Если отметки снимают, в каждом центроиде нужна куча или упорядоченное множество расстояний, и операции стоят O(log² n).
- Лес. Если дерево — лес, как дерево языков, декомпозицию строят в каждой семье отдельно, а вопрос о языке без описанных родственников честно возвращает «нет».
Где работает
Кроме ближайшей отметки, центроиды — главный инструмент разделяй-и-властвуй на деревьях: чтобы сосчитать пути с нужной длиной или весом, каждый путь учитывают в том центроиде, через который он проходит, и в каждом центроиде задача сводится к двум половинам пути. Так решается, например, задача Race с Международной олимпиады 2011 года: путь с суммой весов ровно K и наименьшим числом рёбер. Для вопросов о пути между двумя вершинами с изменениями на нём удобнее тяжёлые пути, для вопросов о расстояниях с отметками — центроиды. В лингвистике и биологии деревья классификации огромны, а вопрос «ближайший описанный родственник» задают постоянно: про языки — по Glottolog, про виды — по таксономии.
История
Центроид дерева ввёл Камиль Жордан в 1869 году в работе о «сборках линий»: он доказал, что у каждого дерева один или два центроида и один или два центра. В олимпиадном программировании центроидное разбиение стало стандартным приёмом разделяй-и-властвуй на деревьях, особенно после задач вроде Race. Каталог Glottolog, на котором построена сцена, составляют Харальд Хаммарстрём, Роберт Форкель, Мартин Хаспельмат и Себастьян Банк; в нём языки, их классификация и самое полное известное описание каждого языка.
Задачи
В задаче отметки и вопросы приходят вперемешку, как в сцене, только без подсказки дерева центроидов. Среди тестов — то же дерево языков с отметками-грамматиками в случайном порядке и длинная цепочка, на которой обход до первой отметки не успевает.
Описанный родственникДанные: Языки мира: Glottolog 5.3 (Хаммарстрём, Форкель, Хаспельмат, Банк, 2026), CC BY 4.0