Small-to-large и DSU on tree: число различных цветов в поддереве за O(n log n)
Переливание меньшего в большее и DSU on tree (sack): почему это O(n log n), как посчитать различные цвета в каждом поддереве и частые ошибки. Код на Python и JavaScript.
Коротко
| Что | Значение |
|---|---|
| Задача | ответить на вопрос про каждое поддерево: сколько различных цветов, какой цвет самый частый, сколько цветов встречается ≥ k раз |
| Наивно | собрать поддерево заново для каждой вершины — |
| Small-to-large | ребёнок отдаёт своё множество, меньшее вливается в большее — операций с множеством |
| DSU on tree (sack) | один глобальный массив счётчиков, тяжёлый сын не стирается — без хеш-таблиц |
| Главная идея | элемент переезжает, только когда размер его множества хотя бы удваивается, а удвоиться можно не больше раз |
Техника выглядит как трюк из олимпиад, но на деле это одна строчка if len(a) < len(b): a, b = b, a, которая превращает квадратичное решение в почти линейное. Та же идея спрятана в объединении по размеру в системе непересекающихся множеств — отсюда и название «DSU on tree».
Задача
Дано корневое дерево из вершин (корень — вершина 0), у каждой вершины есть цвет color[v]. Для каждой вершины нужно узнать, сколько различных цветов встречается в её поддереве.
Пример:
0 (1)
/ \
1 (2) 2 (1)
/ \ \
3 (2) 4 (3) 5 (1)
В скобках — цвет. Ответ: [3, 2, 1, 1, 1, 1]. В поддереве вершины 1 цвета {2, 2, 3} — два различных, в поддереве корня все три.
Если вопрос задан про одно поддерево, хватит одного обхода и множества. Сложность появляется, когда вопросов — по одному на вершину, — а порядка .
Наивное решение:
Для каждой вершины заново обходим её поддерево и складываем цвета в set:
import sys sys.setrecursionlimit(10000) def distinct_naive(n, edges, color): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) ans = [0] * n def collect(v, parent, acc): acc.add(color[v]) for to in graph[v]: if to != parent: collect(to, v, acc) def dfs(v, parent): s = set() collect(v, parent, s) ans[v] = len(s) for to in graph[v]: if to != parent: dfs(to, v) dfs(0, -1) return ans
Каждая вершина попадает в collect столько раз, сколько у неё предков (плюс один). Сумма по всем вершинам — это сумма глубин. Для сбалансированного дерева это , и решение даже пройдёт. Но для «бамбука» — цепочки — сумма глубин равна , то есть при . Это часы.
Шаг к оптимуму: не выбрасывать работу детей
Наивное решение глупо тем, что, посчитав множество цветов для ребёнка, мы его выкидываем, а потом собираем то же самое ещё раз для родителя. Логичнее, чтобы ребёнок отдал родителю своё множество, а родитель объединил множества всех детей и добавил свой цвет.
Но если объединять «как получится», мы ничего не выиграем. Возьмём тот же бамбук и будем каждый раз создавать множество вершины и вливать в него множество ребёнка. Вершина отдаёт 1 элемент, — 2 элемента, и так далее: снова переносов.
Исправление — одна проверка: вливаем меньшее множество в большее, а большее забираем себе целиком, без копирования. В бамбуке у вершины ровно один ребёнок с большим множеством, его мы просто «присваиваем», и переносим только собственный цвет. Итого .
Почему это
Это главное место статьи, и доказательство на удивление короткое.
Следим за одним конкретным элементом . Он физически переносится из множества в множество только тогда, когда . После переноса лежит в множестве размера .
Значит, каждый перенос как минимум удваивает размер множества, в котором живёт . Начинал он в множестве размера 1, а больше размер не бывает. Удвоить 1 до можно не больше чем раз.
Элементов , каждый переносится не больше раз — всего вставок. С хеш-множеством каждая вставка в среднем, итог — . Если вместо set используется сбалансированное дерево (std::set в C++, TreeMap в Java), добавляется ещё логарифм: .
Обратите внимание: доказательство вообще не про деревья. Оно работает для любой последовательности слияний, где меньшее вливается в большее, — поэтому та же оценка верна для объединения по размеру в DSU и для слияния куч, списков, словарей.
Проверим на числах
Посчитаем реальное число переносов для двух стратегий:
def moves(n, edges, smart): g = [[] for _ in range(n)] for u, v in edges: g[u].append(v) total = 0 sets = [None] * n for v in range(n - 1, -1, -1): # дети имеют большие номера cur = [v] for to in g[v]: child = sets[to] if smart and len(child) > len(cur): cur, child = child, cur total += len(child) cur += child sets[v] = cur return total n = 2000 bamboo = [(i - 1, i) for i in range(1, n)] print('бамбук, всегда в текущее:', moves(n, bamboo, False)) print('бамбук, меньшее в большее:', moves(n, bamboo, True)) n = 2 ** 16 - 1 binary = [((i - 1) // 2, i) for i in range(1, n)] print('полное бинарное, меньшее в большее:', moves(n, binary, True)) print('n * log2(n) =', round(n * 16))
бамбук, всегда в текущее: 1999000
бамбук, меньшее в большее: 1999
полное бинарное, меньшее в большее: 491520
n * log2(n) = 1048560
На бамбуке разница в тысячу раз. Худший случай для small-to-large — полное бинарное дерево, где множества братьев одинаковые и каждый раз половина элементов честно переезжает. Но даже там переносов меньше, чем .
Решение 1: переливание множеств
def distinct_colors(n, edges, color): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) # Итеративный DFS: порядок обхода и родитель каждой вершины parent = [-1] * n order = [] stack = [0] seen = [False] * n seen[0] = True while stack: v = stack.pop() order.append(v) for to in graph[v]: if not seen[to]: seen[to] = True parent[to] = v stack.append(to) sets = [None] * n ans = [0] * n # Обратный порядок: дети всегда обрабатываются раньше родителя for v in reversed(order): cur = {color[v]} for to in graph[v]: if to == parent[v]: continue child = sets[to] sets[to] = None # множество ребёнка больше не нужно if len(child) > len(cur): cur, child = child, cur # большее берём себе целиком cur.update(child) # переливаем меньшее sets[v] = cur ans[v] = len(cur) return ans edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)] color = [1, 2, 1, 2, 3, 1] print(distinct_colors(6, edges, color)) # [3, 2, 1, 1, 1, 1]
Разберём на примере, что происходит с вершиной 1:
- Дети 3 и 4 уже обработаны:
sets[3] = {2},sets[4] = {3}. - Начинаем с
cur = {2}(цвет самой вершины 1). - Ребёнок 3:
{2}не большеcur, вливаем —cur = {2}. - Ребёнок 4:
{3}не большеcur, вливаем —cur = {2, 3}. ans[1] = 2, множество{2, 3}уходит наверх, корню.
Корень получит множества {2, 3} от вершины 1 и {1} от вершины 2. Первое больше его собственного {1}, поэтому корень забирает его как своё и доливает туда {1} — копирования двухэлементного множества не происходит.
Почему DFS итеративный: в Python глубина рекурсии по умолчанию 1000, а бамбук из вершин её гарантированно пробьёт. Обратный порядок обхода в глубину (как и в ширину) гарантирует, что каждая вершина обрабатывается после всех своих потомков. Подробнее об обходах — в статье DFS и BFS.
На случайном дереве из вершин это решение у меня отработало примерно за 0,6 секунды на CPython, на бамбуке — за 0,25.
То же на JavaScript
function distinctColors(n, edges, color) { const graph = Array.from({ length: n }, () => []) for (const [u, v] of edges) { graph[u].push(v) graph[v].push(u) } const parent = new Array(n).fill(-1) const order = [0] for (let i = 0; i < order.length; i++) { const v = order[i] for (const to of graph[v]) { if (to !== parent[v]) { parent[to] = v order.push(to) } } } const sets = new Array(n).fill(null) const ans = new Array(n).fill(0) for (let i = n - 1; i >= 0; i--) { const v = order[i] let cur = new Set([color[v]]) for (const to of graph[v]) { if (to === parent[v]) continue let child = sets[to] sets[to] = null if (child.size > cur.size) [cur, child] = [child, cur] for (const c of child) cur.add(c) } sets[v] = cur ans[v] = cur.size } return ans } const edges = [ [0, 1], [0, 2], [1, 3], [1, 4], [2, 5], ] console.log(distinctColors(6, edges, [1, 2, 1, 2, 3, 1])) // [ 3, 2, 1, 1, 1, 1 ]
Здесь порядок получен обходом в ширину: массив order растёт прямо во время цикла, и это тоже корректный порядок «родитель раньше детей».
Решение 2: DSU on tree (sack)
У переливания множеств два минуса: много мелких хеш-таблиц (память и константа) и неудобство, когда вопрос сложнее, чем «сколько различных». Например, «сколько цветов встречается в поддереве хотя бы раз» требует хранить не только множество, но и частоты, и счётчик частот.
Sack решает это одним глобальным массивом cnt[color], общим на всё дерево. Идея:
- Тяжёлый сын вершины — ребёнок с самым большим поддеревом. Остальные — лёгкие.
dfs(v, keep)сначала рекурсивно обрабатывает всех лёгких детей сkeep = False: каждый считает свой ответ и стирает за собой вклад вcnt.- Затем тяжёлого сына с
keep = True: его вклад остаётся вcnt. - Теперь в
cntлежит ровно поддерево тяжёлого сына. Добавляем самуvи заново проходим по всем вершинам лёгких поддеревьев. Вcnt— поддеревоv, записываем ответ. - Если
keep = False, стираем всё поддеревоv.
Чтобы быстро перебирать вершины поддерева без рекурсии, заранее делаем эйлеров обход: поддерево v — это непрерывный отрезок euler[tin[v]:tout[v]]. Тот же приём используется в дереве отрезков на дереве и в heavy-light декомпозиции, откуда и понятие тяжёлого сына.
def subtree_queries(n, edges, color): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) # 1. Эйлеров обход: tin/tout, массив вершин по времени входа parent = [-1] * n tin = [0] * n tout = [0] * n euler = [] stack = [(0, False)] visited = [False] * n while stack: v, done = stack.pop() if done: tout[v] = len(euler) # поддерево v — это euler[tin[v]:tout[v]] continue visited[v] = True tin[v] = len(euler) euler.append(v) stack.append((v, True)) for to in graph[v]: if not visited[to]: parent[to] = v stack.append((to, False)) # 2. Размеры поддеревьев и тяжёлый сын size = [1] * n for v in reversed(euler): if parent[v] != -1: size[parent[v]] += size[v] heavy = [-1] * n for v in range(n): best = 0 for to in graph[v]: if to != parent[v] and size[to] > best: best, heavy[v] = size[to], to cnt = [0] * (max(color) + 1) distinct = 0 ans = [0] * n def add(v, delta): nonlocal distinct c = color[v] if delta == 1: if cnt[c] == 0: distinct += 1 cnt[c] += 1 else: cnt[c] -= 1 if cnt[c] == 0: distinct -= 1 # 3. Сам sack. Стек имитирует рекурсию dfs(v, keep) stack = [(0, True, 0)] while stack: v, keep, phase = stack.pop() if phase == 0: stack.append((v, keep, 1)) if heavy[v] != -1: # кладём первым — снимется со стека последним stack.append((heavy[v], True, 0)) for to in graph[v]: if to != parent[v] and to != heavy[v]: stack.append((to, False, 0)) # лёгкие — раньше тяжёлого else: # Лёгкие дети посчитаны и стёрты, в cnt лежит поддерево heavy[v] add(v, 1) for to in graph[v]: if to != parent[v] and to != heavy[v]: for i in range(tin[to], tout[to]): add(euler[i], 1) ans[v] = distinct if not keep: for i in range(tin[v], tout[v]): add(euler[i], -1) return ans edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)] color = [1, 2, 1, 2, 3, 1] print(subtree_queries(6, edges, color)) # [3, 2, 1, 1, 1, 1]
Рекурсия заменена явным стеком с двумя фазами: «зайти в вершину и запланировать детей» и «все дети готовы, считаем саму вершину». В C++ этот код обычно пишут рекурсивно, и он короче вдвое.
Важная деталь порядка: тяжёлый сын должен обрабатываться последним. Иначе лёгкий ребёнок, стирая себя, будет работать поверх уже заполненного cnt, а следующий лёгкий ребёнок увидит в счётчиках чужие цвета.
Почему sack — тоже
Посмотрим, сколько раз вершина добавляется в cnt. Это происходит, когда какой-то её предок перебирает лёгкое поддерево, содержащее . То есть ровно столько раз, сколько лёгких рёбер на пути от до корня (плюс один раз — когда она сама добавляет себя).
Лёгкое ребро ведёт в поддерево размера не больше половины родительского: если бы лёгкий ребёнок был больше половины, он был бы тяжелее тяжёлого. Значит, при каждом подъёме по лёгкому ребру размер поддерева минимум удваивается, и лёгких рёбер на пути не больше . Это то же самое рассуждение с удвоением, только в другой одежде. Стирания стоят столько же, сколько добавления, поэтому итог — операций add по .
Модификация: самый частый цвет
Классическая задача с Codeforces (600E, «Lomsat gelral»): для каждого поддерева найти сумму всех цветов, которые встречаются в нём максимальное число раз.
С переливанием она решается почти так же. Вместо множества храним словарь частот, текущую максимальную частоту и сумму цветов с этой частотой. При вливании частоты только растут, поэтому максимум можно обновлять на ходу, ничего не пересчитывая:
def dominant_sum(n, edges, color): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) graph[v].append(u) parent = [-1] * n order = [0] for v in order: # BFS: список растёт прямо во время обхода for to in graph[v]: if to != parent[v]: parent[to] = v order.append(to) # Для каждой вершины: [счётчик цветов, макс. частота, сумма цветов с этой частотой] data = [None] * n ans = [0] * n for v in reversed(order): cur = [{color[v]: 1}, 1, color[v]] for to in graph[v]: if to == parent[v]: continue child = data[to] data[to] = None if len(child[0]) > len(cur[0]): cur, child = child, cur cnt = cur[0] for c, k in child[0].items(): f = cnt.get(c, 0) + k cnt[c] = f if f > cur[1]: cur[1], cur[2] = f, c elif f == cur[1]: cur[2] += c data[v] = cur ans[v] = cur[2] return ans edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5)] color = [1, 2, 1, 2, 3, 1] print(dominant_sum(6, edges, color)) # [1, 2, 1, 2, 3, 1]
Сравниваем размеры словарей (число различных цветов), а не суммарные частоты, — ведь переносим мы ключи. Доказательство с удвоением работает и здесь: ключ переезжает только в словарь не меньшего размера.
Обновлять максимум «на ходу» можно только потому, что частоты при слиянии не убывают. Если бы элементы из множества ещё и удалялись, понадобился бы счётчик частот freq[f] — и тогда sack с его глобальными массивами удобнее.
Типичные ошибки
Копирование большего множества. cur = set(child) вместо cur = child молча возвращает квадратичную сложность: вы копируете большое множество целиком на каждом шаге. Большее нужно именно забрать — по ссылке.
Ответ «потом». После того как вершина отдала множество родителю, оно продолжает меняться. Если записать ans[v] = cur (ссылку), а длину брать в конце, все ответы окажутся равны ответу корня. Отвечайте на вопросы про вершину в момент, когда её множество собрано, — ans[v] = len(cur). Если вопросов к вершине несколько (офлайн-запросы), обработайте их все сразу в этот момент.
Сравнение не тех размеров. Решение о том, что куда вливать, должно опираться на то, что реально переносится: число элементов множества или ключей словаря. Сравнивать размеры поддеревьев для словаря частот формально тоже даёт , но легко запутаться и сравнить вообще не то.
Рекурсия в Python. Бамбук на вершин падает с RecursionError, а sys.setrecursionlimit(10**6) часто роняет интерпретатор уже по переполнению стека C. Надёжнее итеративный обход, как в примерах выше.
Sack: очистка всего массива. Стирать cnt нужно, проходя по вершинам поддерева, а не cnt = [0] * C. Иначе каждая очистка стоит , и при получается .
Sack: тяжёлый сын не последним. Описано выше: лёгкие дети должны отработать и убрать за собой до того, как тяжёлый заполнит счётчики.
Где встречается
На обычных собеседованиях в продуктовые компании small-to-large прямо спрашивают редко — это скорее олимпиадная техника. Но задачи, где она даёт самое чистое решение, есть и на LeetCode:
- 1519. Number of Nodes in the Sub-Tree With the Same Label — для каждой вершины посчитать, сколько вершин в её поддереве с той же меткой. Там всего 26 меток, поэтому хватает массива из 26 счётчиков на вершину, но это хорошая разминка.
- 2003. Smallest Missing Genetic Value in Each Subtree — найти минимальное отсутствующее значение в каждом поддереве. Решается переливанием множеств (есть и более хитрое линейное решение).
На Codeforces техника встречается часто: 600E «Lomsat gelral» (разобрана выше), 375D «Tree and Queries» (цвета, встречающиеся хотя бы раз), 570D «Tree Requests» (запросы по глубине в поддереве), 208E и 246E «Blood Cousins» и «Blood Cousins Return».
Если на интервью звучит «для каждой вершины дерева посчитайте что-то про всё её поддерево», а это «что-то» не складывается из ответов детей числом (как размер или сумма в ДП на деревьях), — почти наверняка нужен small-to-large. Хороший ход — сначала озвучить наивное , показать бамбук как худший случай, а потом предложить вливать меньшее в большее и проговорить доказательство с удвоением. Само доказательство в три строки обычно ценится больше, чем код.
Где ещё работает идея «меньшее в большее»
- DSU с объединением по размеру: при слиянии компонент к большей подвешиваем меньшую, и глубина дерева не превышает . Это та же оценка: вершина опускается на уровень, только когда размер её компоненты удваивается.
- Слияние компонент со списками элементов: если вместе с DSU нужно хранить список вершин компоненты (например, чтобы перекрасить их), переливание меньшего списка в больший даёт суммарно.
- Удаление рёбер из леса: когда ребро разрезает дерево на две части, новый номер компоненты достаточно раздать меньшей части. Чтобы найти её, не обходя большую, запускают два обхода из концов ребра поочерёдно, по шагу, и останавливаются, как только один из них закончится.
Во всех случаях работает одно рассуждение: каждый раз, когда элемент «платит» за операцию, его множество как минимум удваивается, а удваиваться ему некуда больше раз.