Small-to-large и DSU on tree: число различных цветов в поддереве за O(n log n)

Переливание меньшего в большее и DSU on tree (sack): почему это O(n log n), как посчитать различные цвета в каждом поддереве и частые ошибки. Код на Python и JavaScript.

13 мин чтенияалгоритмы · деревья · python

Коротко

ЧтоЗначение
Задачаответить на вопрос про каждое поддерево: сколько различных цветов, какой цвет самый частый, сколько цветов встречается ≥ k раз
Наивнособрать поддерево заново для каждой вершины — O(n2)O(n^2)
Small-to-largeребёнок отдаёт своё множество, меньшее вливается в большее — O(nlog⁡n)O(n \log n) операций с множеством
DSU on tree (sack)один глобальный массив счётчиков, тяжёлый сын не стирается — O(nlog⁡n)O(n \log n) без хеш-таблиц
Главная идеяэлемент переезжает, только когда размер его множества хотя бы удваивается, а удвоиться можно не больше log⁡2n\log_2 n раз

Техника выглядит как трюк из олимпиад, но на деле это одна строчка if len(a) < len(b): a, b = b, a, которая превращает квадратичное решение в почти линейное. Та же идея спрятана в объединении по размеру в системе непересекающихся множеств — отсюда и название «DSU on tree».

Задача

Дано корневое дерево из nn вершин (корень — вершина 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} — два различных, в поддереве корня все три.

Если вопрос задан про одно поддерево, хватит одного обхода и множества. Сложность появляется, когда вопросов nn — по одному на вершину, — а nn порядка 2⋅1052 \cdot 10^5.

Наивное решение: O(n2)O(n^2)

Для каждой вершины заново обходим её поддерево и складываем цвета в 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 столько раз, сколько у неё предков (плюс один). Сумма по всем вершинам — это сумма глубин. Для сбалансированного дерева это O(nlog⁡n)O(n \log n), и решение даже пройдёт. Но для «бамбука» — цепочки 0−1−2−⋯−(n−1)0 - 1 - 2 - \dots - (n-1) — сумма глубин равна n(n−1)/2n(n-1)/2, то есть 2⋅10102 \cdot 10^{10} при n=2⋅105n = 2 \cdot 10^5. Это часы.

Шаг к оптимуму: не выбрасывать работу детей

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

Но если объединять «как получится», мы ничего не выиграем. Возьмём тот же бамбук и будем каждый раз создавать множество вершины и вливать в него множество ребёнка. Вершина n−1n-1 отдаёт 1 элемент, n−2n-2 — 2 элемента, и так далее: снова n(n−1)/2n(n-1)/2 переносов.

Исправление — одна проверка: вливаем меньшее множество в большее, а большее забираем себе целиком, без копирования. В бамбуке у вершины ровно один ребёнок с большим множеством, его мы просто «присваиваем», и переносим только собственный цвет. Итого O(n)O(n).

Почему это O(nlog⁡n)O(n \log n)

Это главное место статьи, и доказательство на удивление короткое.

Следим за одним конкретным элементом xx. Он физически переносится из множества AA в множество BB только тогда, когда ∣A∣≤∣B∣|A| \le |B|. После переноса xx лежит в множестве размера ∣A∣+∣B∣≥2∣A∣|A| + |B| \ge 2|A|.

Значит, каждый перенос как минимум удваивает размер множества, в котором живёт xx. Начинал он в множестве размера 1, а больше nn размер не бывает. Удвоить 1 до nn можно не больше чем log⁡2n\log_2 n раз.

1→2→4→⋯→2k≤n⇒k≤log⁡2n1 \to 2 \to 4 \to \dots \to 2^k \le n \quad\Rightarrow\quad k \le \log_2 n

Элементов nn, каждый переносится не больше log⁡2n\log_2 n раз — всего O(nlog⁡n)O(n \log n) вставок. С хеш-множеством каждая вставка O(1)O(1) в среднем, итог — O(nlog⁡n)O(n \log n). Если вместо set используется сбалансированное дерево (std::set в C++, TreeMap в Java), добавляется ещё логарифм: O(nlog⁡2n)O(n \log^2 n).

Обратите внимание: доказательство вообще не про деревья. Оно работает для любой последовательности слияний, где меньшее вливается в большее, — поэтому та же оценка верна для объединения по размеру в 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 — полное бинарное дерево, где множества братьев одинаковые и каждый раз половина элементов честно переезжает. Но даже там переносов меньше, чем nlog⁡2nn \log_2 n.

Решение 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:

  1. Дети 3 и 4 уже обработаны: sets[3] = {2}, sets[4] = {3}.
  2. Начинаем с cur = {2} (цвет самой вершины 1).
  3. Ребёнок 3: {2} не больше cur, вливаем — cur = {2}.
  4. Ребёнок 4: {3} не больше cur, вливаем — cur = {2, 3}.
  5. ans[1] = 2, множество {2, 3} уходит наверх, корню.

Корень получит множества {2, 3} от вершины 1 и {1} от вершины 2. Первое больше его собственного {1}, поэтому корень забирает его как своё и доливает туда {1} — копирования двухэлементного множества не происходит.

Почему DFS итеративный: в Python глубина рекурсии по умолчанию 1000, а бамбук из 2⋅1052 \cdot 10^5 вершин её гарантированно пробьёт. Обратный порядок обхода в глубину (как и в ширину) гарантирует, что каждая вершина обрабатывается после всех своих потомков. Подробнее об обходах — в статье DFS и BFS.

На случайном дереве из 2⋅1052 \cdot 10^5 вершин это решение у меня отработало примерно за 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)

У переливания множеств два минуса: много мелких хеш-таблиц (память и константа) и неудобство, когда вопрос сложнее, чем «сколько различных». Например, «сколько цветов встречается в поддереве хотя бы kk раз» требует хранить не только множество, но и частоты, и счётчик частот.

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 — тоже O(nlog⁡n)O(n \log n)

Посмотрим, сколько раз вершина uu добавляется в cnt. Это происходит, когда какой-то её предок vv перебирает лёгкое поддерево, содержащее uu. То есть ровно столько раз, сколько лёгких рёбер на пути от uu до корня (плюс один раз — когда она сама добавляет себя).

Лёгкое ребро ведёт в поддерево размера не больше половины родительского: если бы лёгкий ребёнок был больше половины, он был бы тяжелее тяжёлого. Значит, при каждом подъёме по лёгкому ребру размер поддерева минимум удваивается, и лёгких рёбер на пути не больше log⁡2n\log_2 n. Это то же самое рассуждение с удвоением, только в другой одежде. Стирания стоят столько же, сколько добавления, поэтому итог — O(nlog⁡n)O(n \log n) операций add по O(1)O(1).

Модификация: самый частый цвет

Классическая задача с 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). Если вопросов к вершине несколько (офлайн-запросы), обработайте их все сразу в этот момент.

Сравнение не тех размеров. Решение о том, что куда вливать, должно опираться на то, что реально переносится: число элементов множества или ключей словаря. Сравнивать размеры поддеревьев для словаря частот формально тоже даёт O(nlog⁡n)O(n \log n), но легко запутаться и сравнить вообще не то.

Рекурсия в Python. Бамбук на 10510^5 вершин падает с RecursionError, а sys.setrecursionlimit(10**6) часто роняет интерпретатор уже по переполнению стека C. Надёжнее итеративный обход, как в примерах выше.

Sack: очистка всего массива. Стирать cnt нужно, проходя по вершинам поддерева, а не cnt = [0] * C. Иначе каждая очистка стоит O(C)O(C), и при C∼nC \sim n получается O(n2)O(n^2).

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» (цвета, встречающиеся хотя бы kk раз), 570D «Tree Requests» (запросы по глубине в поддереве), 208E и 246E «Blood Cousins» и «Blood Cousins Return».

Если на интервью звучит «для каждой вершины дерева посчитайте что-то про всё её поддерево», а это «что-то» не складывается из ответов детей числом (как размер или сумма в ДП на деревьях), — почти наверняка нужен small-to-large. Хороший ход — сначала озвучить наивное O(n2)O(n^2), показать бамбук как худший случай, а потом предложить вливать меньшее в большее и проговорить доказательство с удвоением. Само доказательство в три строки обычно ценится больше, чем код.

Где ещё работает идея «меньшее в большее»

  • DSU с объединением по размеру: при слиянии компонент к большей подвешиваем меньшую, и глубина дерева не превышает log⁡2n\log_2 n. Это та же оценка: вершина опускается на уровень, только когда размер её компоненты удваивается.
  • Слияние компонент со списками элементов: если вместе с DSU нужно хранить список вершин компоненты (например, чтобы перекрасить их), переливание меньшего списка в больший даёт O(nlog⁡n)O(n \log n) суммарно.
  • Удаление рёбер из леса: когда ребро разрезает дерево на две части, новый номер компоненты достаточно раздать меньшей части. Чтобы найти её, не обходя большую, запускают два обхода из концов ребра поочерёдно, по шагу, и останавливаются, как только один из них закончится.

Во всех случаях работает одно рассуждение: каждый раз, когда элемент «платит» за операцию, его множество как минимум удваивается, а удваиваться ему некуда больше log⁡2n\log_2 n раз.

Потренироваться в спокойной обстановке

Все задачи