Эйлеров обход дерева: tin/tout и запросы на поддеревьях
Эйлеров обход дерева простыми словами: времена входа и выхода tin/tout, проверка «предок ли» за O(1), сумма на поддереве и на пути до корня через Фенвика. Код на Python.
Коротко
| Что нужно | Как делает Эйлеров обход | Сложность |
|---|---|---|
Проверить, что u — предок v | tin[u] <= tin[v] <= tout[u] | после |
| Сумма/минимум на поддереве | запрос на отрезке [tin[v], tout[v]] | |
| Изменить значение вершины | точечное обновление в позиции tin[v] | |
Сумма на пути от корня до v | прибавление на отрезке + запрос в точке | |
| LCA | минимум глубины на полном обходе длины | со sparse table |
Главная идея: один DFS раскладывает дерево в массив так, что любое поддерево превращается в непрерывный отрезок. После этого задачи про поддеревья решаются обычными структурами для массивов — деревом Фенвика или деревом отрезков.
Это не эйлеров путь в графе
Название сбивает с толку. Есть две разные вещи с фамилией Эйлера:
- Эйлеров путь в графе — маршрут, проходящий по каждому ребру ровно один раз. Существует не всегда, ищется алгоритмом Хирхольцера. Про него есть отдельная статья.
- Эйлеров обход дерева (Euler tour technique) — запись вершин в порядке обхода в глубину. Существует всегда, строится обычным DFS.
Связь между ними есть: если каждое ребро дерева заменить двумя ориентированными (туда и обратно), то DFS обходит каждое из них ровно один раз — то есть получается эйлеров цикл в этом удвоенном графе. Отсюда и название. Но на практике про это можно забыть: техника — это просто DFS с таймером.
Задача, которая всё объясняет
Дано корневое дерево из вершин, в каждой записано число. Приходят запросы двух типов:
- изменить число в вершине
v; - посчитать сумму чисел в поддереве
v.
Наивное решение — на каждый запрос второго типа запускать DFS из v. Это на запрос, а при получаем операций. Не годится.
Можно хранить для каждой вершины готовую сумму поддерева. Тогда запрос — , но изменение вершины требует обновить всех её предков, а на дереве-«бамбуке» их .
Нужна структура, где обе операции логарифмические. Для массива такая есть — Фенвик: точечное обновление и сумма на отрезке. Осталось превратить дерево в массив так, чтобы поддерево стало отрезком.
Времена входа и выхода
Запустим DFS из корня и заведём счётчик timer. Когда впервые заходим в вершину v, записываем tin[v] = timer и увеличиваем счётчик. Когда обработали всех потомков и уходим из v, записываем tout[v] — последнее выданное время.
Возьмём дерево с корнем 0:
0
/ \
1 2
/ \ \
3 4 5
|
6
DFS посещает вершины в порядке 0, 1, 3, 4, 6, 2, 5. Получаем:
| Вершина | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
tin | 0 | 1 | 5 | 2 | 3 | 6 | 4 |
tout | 6 | 4 | 6 | 2 | 4 | 6 | 4 |
Смотрим на массив order — вершины в порядке входа:
позиция: 0 1 2 3 4 5 6
order: 0 1 3 4 6 2 5
└──────────┘ поддерево 1 = позиции [1, 4]
└────┘ поддерево 2 = позиции [5, 6]
Поддерево вершины 1 — это {1, 3, 4, 6}, и оно занимает ровно позиции с tin[1] = 1 по tout[1] = 4. Это не совпадение.
Почему поддерево — отрезок
DFS, зайдя в v, не выходит из неё, пока не посетит всех её потомков. Значит, все потомки получают времена входа подряд, сразу после v. А как только DFS покинул v, он уже не вернётся в её поддерево. Поэтому:
Размер поддерева тоже получается бесплатно: tout[v] - tin[v] + 1.
Код: рекурсивный DFS
def euler_tour_recursive(n, adj, root=0): tin = [0] * n tout = [0] * n order = [] timer = 0 def dfs(v, parent): nonlocal timer tin[v] = timer order.append(v) timer += 1 for u in adj[v]: if u != parent: dfs(u, v) tout[v] = timer - 1 dfs(root, -1) return tin, tout, order
adj — список смежности неориентированного дерева, поэтому родителя пропускаем через parent.
Код короткий, но на Python у него есть проблема: лимит рекурсии по умолчанию — 1000. Дерево-цепочка из вершин уронит программу с RecursionError, а sys.setrecursionlimit спасает не всегда — может переполниться уже системный стек. На собеседовании достаточно рекурсивной версии и упоминания проблемы, в реальном коде и на контестах лучше итеративная.
Код: итеративный DFS
Храним стек вершин и для каждой — индекс следующего соседа, которого ещё не смотрели. Вершина снимается со стека, когда соседи кончились: это и есть момент выхода.
def euler_tour(n, adj, root=0): tin = [0] * n tout = [0] * n order = [root] parent = [-1] * n it = [0] * n # индекс следующего соседа для каждой вершины stack = [root] timer = 1 # корень уже получил tin = 0 while stack: v = stack[-1] if it[v] < len(adj[v]): u = adj[v][it[v]] it[v] += 1 if u != parent[v]: parent[u] = v tin[u] = timer order.append(u) timer += 1 stack.append(u) else: tout[v] = timer - 1 stack.pop() return tin, tout, order
Обе версии дают одинаковый результат (порядок соседей тот же), а итеративная спокойно переваривает цепочку из 200 000 вершин.
Проверим на дереве из примера:
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6)] n = 7 adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b) adj[b].append(a) tin, tout, order = euler_tour(n, adj) print(order) # [0, 1, 3, 4, 6, 2, 5] print(tin) # [0, 1, 5, 2, 3, 6, 4] print(tout) # [6, 4, 6, 2, 4, 6, 4]
Применение 1: «является ли u предком v» за O(1)
Классический вопрос: даны две вершины, лежит ли одна на пути от корня к другой? Без предподсчёта придётся подниматься от v к корню — , где — высота дерева.
С tin/tout это одно сравнение:
def is_ancestor(u, v, tin, tout): """u — предок v (или u == v)?""" return tin[u] <= tin[v] <= tout[u] print(is_ancestor(1, 6, tin, tout)) # True print(is_ancestor(2, 6, tin, tout)) # False
Эта проверка — строительный блок для других алгоритмов. Например, в LCA через двоичные подъёмы именно она решает, нужно ли прыгать вверх: «если up[u][k] ещё не предок v — прыгаем».
Если нужен строгий предок, добавьте u != v.
Применение 2: сумма на поддереве с обновлениями
Вернёмся к исходной задаче. Положим значение вершины v в позицию tin[v] массива. Теперь:
- изменить значение вершины — точечное обновление в
tin[v]; - сумма поддерева — сумма на отрезке
[tin[v], tout[v]].
Обе операции Фенвик делает за :
class Fenwick: def __init__(self, n): self.n = n self.t = [0] * (n + 1) def add(self, i, delta): # i — индекс с нуля i += 1 while i <= self.n: self.t[i] += delta i += i & -i def prefix(self, i): # сумма на [0, i] i += 1 s = 0 while i > 0: s += self.t[i] i -= i & -i return s def range_sum(self, l, r): return self.prefix(r) - (self.prefix(l - 1) if l > 0 else 0) class SubtreeSum: def __init__(self, n, adj, values, root=0): self.tin, self.tout, _ = euler_tour(n, adj, root) self.values = values[:] self.fw = Fenwick(n) for v in range(n): self.fw.add(self.tin[v], values[v]) def set_value(self, v, x): self.fw.add(self.tin[v], x - self.values[v]) self.values[v] = x def subtree_sum(self, v): return self.fw.range_sum(self.tin[v], self.tout[v])
На нашем дереве:
values = [5, 3, 8, 1, 4, 2, 7] st = SubtreeSum(n, adj, values) print(st.subtree_sum(1)) # 3 + 1 + 4 + 7 = 15 st.set_value(6, 10) print(st.subtree_sum(1)) # 18 print(st.subtree_sum(0)) # 33
Частая ошибка — положить значение в позицию v, а не tin[v]. Тогда отрезок [tin[v], tout[v]] будет содержать случайные вершины, а код при этом не упадёт и на маленьком тесте может даже случайно совпасть с ответом.
Минимум, максимум и другие операции
Фенвик удобен для сумм, но минимум на произвольном отрезке с обновлениями он не умеет. Тогда берите дерево отрезков поверх того же массива: «максимум в поддереве», «количество вершин со значением больше k», что угодно, что дерево отрезков умеет на отрезке.
Если обновление тоже касается целого поддерева («прибавь x ко всем вершинам поддерева v» и «сумма поддерева»), это прибавление на отрезке плюс сумма на отрезке — нужно дерево отрезков с отложенными операциями или Фенвик на двух массивах.
Если обновлений нет вовсе, хватит префиксных сумм или sparse table для минимума.
Применение 3: сумма на пути от корня до вершины
Задача-перевёртыш: значения в вершинах меняются, а запрос — сумма на пути от корня до v.
Посмотрим, на какие запросы влияет значение вершины u. Оно входит в путь от корня до v ровно тогда, когда u — предок v, то есть v лежит в поддереве u. Значит, изменение значения u на delta — это «прибавить delta ко всем позициям отрезка [tin[u], tout[u]]», а запрос для v — «прочитать значение в точке tin[v]».
Прибавление на отрезке и запрос в точке — стандартный трюк с Фенвиком на разностях: +delta в начало отрезка, -delta сразу после конца, а значение в точке — префиксная сумма.
class PathToRootSum: """Значения в вершинах, запрос — сумма на пути от корня до v.""" def __init__(self, n, adj, values, root=0): self.tin, self.tout, _ = euler_tour(n, adj, root) self.values = [0] * n self.fw = Fenwick(n + 1) # +1: пишем в позицию tout + 1 for v in range(n): self.set_value(v, values[v]) def set_value(self, v, x): delta = x - self.values[v] self.values[v] = x # значение v входит в ответ для всех вершин её поддерева self.fw.add(self.tin[v], delta) self.fw.add(self.tout[v] + 1, -delta) def path_sum(self, v): return self.fw.prefix(self.tin[v])
ps = PathToRootSum(n, adj, values) print(ps.path_sum(6)) # 5 + 3 + 4 + 7 = 19 ps.set_value(1, 0) print(ps.path_sum(6)) # 16 print(ps.path_sum(5)) # 5 + 8 + 2 = 15
А сумма на пути между любыми двумя вершинами получается через LCA:
где — сумма от корня до . Для минимума на пути такой фокус не работает (минимум нельзя «вычесть») — там нужна тяжёлая-лёгкая декомпозиция.
Применение 4: сколько потомков на глубине d
Ещё одна задача, которую линеаризация решает почти без кода: «сколько вершин поддерева v находится на глубине d от корня?». Обновлений нет, запросов много.
Сгруппируем вершины по глубине и для каждой глубины сохраним список их tin. Вершины на глубине d внутри поддерева v — это ровно те, чей tin попадает в [tin[v], tout[v]]. Если список отсортирован, ответ — два бинарных поиска.
from bisect import bisect_left, bisect_right from collections import defaultdict class DepthCounter: """Сколько вершин поддерева v лежит на глубине d.""" def __init__(self, n, adj, root=0): self.tin, self.tout, order = euler_tour(n, adj, root) depth = [0] * n self.by_depth = defaultdict(list) for v in order: # родитель всегда раньше ребёнка for u in adj[v]: if self.tin[u] > self.tin[v]: # u — ребёнок v depth[u] = depth[v] + 1 self.by_depth[depth[v]].append(self.tin[v]) # списки уже отсортированы: order идёт по возрастанию tin def count(self, v, d): times = self.by_depth.get(d, []) lo = bisect_left(times, self.tin[v]) hi = bisect_right(times, self.tout[v]) return hi - lo dc = DepthCounter(n, adj) print(dc.count(0, 2)) # 3: вершины 3, 4, 5 print(dc.count(1, 2)) # 2: вершины 3, 4 print(dc.count(2, 3)) # 0
Сортировать ничего не пришлось: мы идём по order, то есть по возрастанию tin, и дописываем в конец списков. Предподсчёт , запрос .
Обратите внимание на проверку tin[u] > tin[v]: в неориентированном списке смежности среди соседей v есть и родитель, а у него tin меньше. Это тот же is_ancestor, только в упрощённом виде для соседних вершин.
Похожим образом решается «сколько вершин поддерева имеют значение меньше k»: нужно посчитать элементы меньше k на отрезке массива. Офлайн это делается сортировкой запросов и Фенвиком, онлайн — деревом отрезков с отсортированными списками в узлах.
Разбор задачи: оргструктура
Сформулируем задачу так, как её могут дать на собеседовании.
В компании сотрудников, у каждого, кроме CEO, есть один непосредственный руководитель. Приходят запросы: «является ли сотрудник A руководителем B — прямым или через несколько уровней?». Запросов до , сотрудников до .
Шаг 1. Наивно. Поднимаемся от B по руководителям, пока не встретим A или не дойдём до CEO. Сложность на запрос. В плоской компании это быстро, но если оргструктура — длинная цепочка, получаем .
Шаг 2. Наблюдение. «A — руководитель B» означает, что B лежит в поддереве A. Поддерево после DFS — отрезок времён входа.
Шаг 3. Решение. Строим список детей по массиву руководителей, один итеративный DFS от CEO, затем каждый запрос — tin[A] <= tin[B] <= tout[A]. Итого .
Шаг 4. Уточнения, о которых стоит спросить. Считается ли сотрудник руководителем самого себя? Может ли структура меняться между запросами? Если сотрудников переводят из отдела в отдел, статичный tin/tout уже не работает — нужны динамические деревья (link-cut tree или Euler tour tree), а это уже уровень олимпиады, а не собеседования. Если просто нанимают новых людей «в листья», задачу можно решить офлайн: сначала прочитать все события, построить итоговое дерево и отвечать по нему. Новый лист не меняет отношение «предок — потомок» между теми, кто уже работал, поэтому ответы останутся верными.
Полный эйлеров обход и LCA
У техники есть второй вариант: записывать вершину не только при входе, но и каждый раз, когда возвращаемся в неё из ребёнка. Получается последовательность длины :
def full_euler_tour(n, adj, root=0): tour = [] first = [0] * n def dfs(v, parent): first[v] = len(tour) tour.append(v) for u in adj[v]: if u != parent: dfs(u, v) tour.append(v) # вернулись в v из ребёнка dfs(root, -1) return tour, first tour, first = full_euler_tour(n, adj) print(tour) # [0, 1, 3, 1, 4, 6, 4, 1, 0, 2, 5, 2, 0] print(first) # [0, 1, 9, 2, 4, 10, 5]
Это и есть тот самый эйлеров цикл по удвоенным рёбрам. Его ключевое свойство: между первыми вхождениями u и v обход обязательно проходит через их LCA, и ни через одну вершину выше. Поэтому LCA — это вершина с минимальной глубиной на отрезке tour[first[u] .. first[v]].
Например, для вершин 3 и 6: tour[2..5] = 3, 1, 4, 6, самая высокая вершина — 1. Это и есть их общий предок.
Так задача LCA сводится к RMQ, а RMQ на статичном массиве решается sparse table за на запрос после предподсчёта. Подробный разбор — в статье про наименьшего общего предка.
Какой вариант когда
| Вариант | Длина | Для чего |
|---|---|---|
Только вход (tin, tout = последнее tin в поддереве) | запросы на поддеревьях, «предок ли» | |
| Вход и выход, таймер растёт на обоих | «предок ли», некоторые задачи на путях | |
| Полный обход (запись при каждом возврате) | LCA через RMQ |
Во втором варианте tout[v] получает собственное время при выходе, и проверка предка становится tin[u] < tin[v] and tout[v] < tout[u]. Для отрезков поддеревьев он неудобен: в массиве оказываются «пустые» позиции выходов. Если сомневаетесь — берите первый вариант, он закрывает большинство задач.
Сложность
- Построение
tin,tout,order: времени и памяти — один DFS. - Проверка «предок ли»: .
- Запрос и обновление на поддереве через Фенвик или дерево отрезков: .
- LCA через полный обход и sparse table: предподсчёт, запрос.
Типичные ошибки
- Путают вершину и её позицию. В Фенвик кладётся
values[v]по индексуtin[v], а если нужно восстановить вершину по позиции —order[i]. Помогает дисциплина в именах:vдля вершин,iилиposдля позиций. toutна единицу больше. Если писатьtout[v] = timerпосле цикла (а неtimer - 1), получится полуинтервал[tin, tout). Это тоже рабочий вариант, но смешивать его с закрытыми отрезками в запросах нельзя — выберите один и придерживайтесь его.- Рекурсия на Python. Бамбук из вершин — стандартный тест. Пишите итеративный DFS.
- Не тот корень. Если в условии дерево задано рёбрами без корня, а запросы про «поддерево», корень обычно указан явно (часто вершина 1 при нумерации с единицы). Обход от другого корня даст другие поддеревья.
- Разные обходы для разных структур. Если строить
tinв одном месте программы, а потом ещё раз в другом с другим порядком соседей, отрезки перестанут совпадать. Посчитайте один раз и передавайте.
Где встречается на собеседованиях
Сама формулировка «Эйлеров обход» на интервью звучит редко, зато задачи, где он — самое чистое решение, встречаются:
- «Является ли A руководителем B» в оргструктуре компании, много запросов. Это ровно
is_ancestor. Наивное «поднимаемся по начальникам» — хороший старт, предподсчётtin/tout— ожидаемое улучшение. - Сумма/количество в поддереве с изменениями: зарплатный фонд отдела, число активных файлов в папке файловой системы, количество комментариев в ветке обсуждения.
- LCA — тут Эйлеров обход идёт как один из способов наряду с двоичными подъёмами.
- Олимпиадные задачи: «количество различных цветов в поддереве» (линеаризация плюс офлайн-обработка запросов-отрезков, например алгоритмом Мо), «k-й по величине элемент поддерева», прибавление на поддереве.
Хорошая подача на интервью: сначала проговорить, что поддерево после DFS — непрерывный отрезок, и объяснить почему. Дальше задача сводится к «известной структуре на массиве», и интервьюер это сразу оценит.
Итог
Эйлеров обход дерева — это DFS с таймером, который превращает дерево в массив. Поддерево становится отрезком [tin[v], tout[v]], проверка предка — двумя сравнениями, а вся мощь Фенвика и дерева отрезков становится доступна для деревьев. Если в задаче есть слово «поддерево» и много запросов — почти наверняка начинать стоит с tin и tout.
Чтобы закрепить базу, полезно повторить обходы в глубину и ширину и динамику на деревьях: многие задачи на поддеревья без обновлений решаются одним DFS, и линеаризация там не нужна.