Эйлеров обход дерева: tin/tout и запросы на поддеревьях

Эйлеров обход дерева простыми словами: времена входа и выхода tin/tout, проверка «предок ли» за O(1), сумма на поддереве и на пути до корня через Фенвика. Код на Python.

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

Коротко

Что нужноКак делает Эйлеров обходСложность
Проверить, что u — предок vtin[u] <= tin[v] <= tout[u]O(1)O(1) после O(n)O(n)
Сумма/минимум на поддеревезапрос на отрезке [tin[v], tout[v]]O(log⁡n)O(\log n)
Изменить значение вершиныточечное обновление в позиции tin[v]O(log⁡n)O(\log n)
Сумма на пути от корня до vприбавление на отрезке + запрос в точкеO(log⁡n)O(\log n)
LCAминимум глубины на полном обходе длины 2n−12n - 1O(1)O(1) со sparse table

Главная идея: один DFS раскладывает дерево в массив так, что любое поддерево превращается в непрерывный отрезок. После этого задачи про поддеревья решаются обычными структурами для массивов — деревом Фенвика или деревом отрезков.

Это не эйлеров путь в графе

Название сбивает с толку. Есть две разные вещи с фамилией Эйлера:

  • Эйлеров путь в графе — маршрут, проходящий по каждому ребру ровно один раз. Существует не всегда, ищется алгоритмом Хирхольцера. Про него есть отдельная статья.
  • Эйлеров обход дерева (Euler tour technique) — запись вершин в порядке обхода в глубину. Существует всегда, строится обычным DFS.

Связь между ними есть: если каждое ребро дерева заменить двумя ориентированными (туда и обратно), то DFS обходит каждое из них ровно один раз — то есть получается эйлеров цикл в этом удвоенном графе. Отсюда и название. Но на практике про это можно забыть: техника — это просто DFS с таймером.

Задача, которая всё объясняет

Дано корневое дерево из nn вершин, в каждой записано число. Приходят запросы двух типов:

  1. изменить число в вершине v;
  2. посчитать сумму чисел в поддереве v.

Наивное решение — на каждый запрос второго типа запускать DFS из v. Это O(n)O(n) на запрос, а при n=q=105n = q = 10^5 получаем 101010^{10} операций. Не годится.

Можно хранить для каждой вершины готовую сумму поддерева. Тогда запрос — O(1)O(1), но изменение вершины требует обновить всех её предков, а на дереве-«бамбуке» их O(n)O(n).

Нужна структура, где обе операции логарифмические. Для массива такая есть — Фенвик: точечное обновление и сумма на отрезке. Осталось превратить дерево в массив так, чтобы поддерево стало отрезком.

Времена входа и выхода

Запустим 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. Получаем:

Вершина0123456
tin0152364
tout6462464

Смотрим на массив 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, он уже не вернётся в её поддерево. Поэтому:

u лежит в поддереве v  ⟺  tin[v]≤tin[u]≤tout[v]u \text{ лежит в поддереве } v \iff tin[v] \le tin[u] \le tout[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. Дерево-цепочка из 10510^5 вершин уронит программу с 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 к корню — O(h)O(h), где hh — высота дерева.

С 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]].

Обе операции Фенвик делает за O(log⁡n)O(\log n):

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:

path(u,v)=root(u)+root(v)−2⋅root(lca)+val(lca)\text{path}(u, v) = \text{root}(u) + \text{root}(v) - 2 \cdot \text{root}(\text{lca}) + \text{val}(\text{lca})

где root(x)\text{root}(x) — сумма от корня до xx. Для минимума на пути такой фокус не работает (минимум нельзя «вычесть») — там нужна тяжёлая-лёгкая декомпозиция.

Применение 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, и дописываем в конец списков. Предподсчёт O(n)O(n), запрос O(log⁡n)O(\log n).

Обратите внимание на проверку tin[u] > tin[v]: в неориентированном списке смежности среди соседей v есть и родитель, а у него tin меньше. Это тот же is_ancestor, только в упрощённом виде для соседних вершин.

Похожим образом решается «сколько вершин поддерева имеют значение меньше k»: нужно посчитать элементы меньше k на отрезке массива. Офлайн это делается сортировкой запросов и Фенвиком, онлайн — деревом отрезков с отсортированными списками в узлах.

Разбор задачи: оргструктура

Сформулируем задачу так, как её могут дать на собеседовании.

В компании nn сотрудников, у каждого, кроме CEO, есть один непосредственный руководитель. Приходят запросы: «является ли сотрудник A руководителем B — прямым или через несколько уровней?». Запросов до 10510^5, сотрудников до 10510^5.

Шаг 1. Наивно. Поднимаемся от B по руководителям, пока не встретим A или не дойдём до CEO. Сложность O(h)O(h) на запрос. В плоской компании это быстро, но если оргструктура — длинная цепочка, получаем O(n⋅q)=1010O(n \cdot q) = 10^{10}.

Шаг 2. Наблюдение. «A — руководитель B» означает, что B лежит в поддереве A. Поддерево после DFS — отрезок времён входа.

Шаг 3. Решение. Строим список детей по массиву руководителей, один итеративный DFS от CEO, затем каждый запрос — tin[A] <= tin[B] <= tout[A]. Итого O(n+q)O(n + q).

Шаг 4. Уточнения, о которых стоит спросить. Считается ли сотрудник руководителем самого себя? Может ли структура меняться между запросами? Если сотрудников переводят из отдела в отдел, статичный tin/tout уже не работает — нужны динамические деревья (link-cut tree или Euler tour tree), а это уже уровень олимпиады, а не собеседования. Если просто нанимают новых людей «в листья», задачу можно решить офлайн: сначала прочитать все события, построить итоговое дерево и отвечать по нему. Новый лист не меняет отношение «предок — потомок» между теми, кто уже работал, поэтому ответы останутся верными.

Полный эйлеров обход и LCA

У техники есть второй вариант: записывать вершину не только при входе, но и каждый раз, когда возвращаемся в неё из ребёнка. Получается последовательность длины 2n−12n - 1:

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 за O(1)O(1) на запрос после O(nlog⁡n)O(n \log n) предподсчёта. Подробный разбор — в статье про наименьшего общего предка.

Какой вариант когда

ВариантДлинаДля чего
Только вход (tin, tout = последнее tin в поддереве)nnзапросы на поддеревьях, «предок ли»
Вход и выход, таймер растёт на обоих2n2n«предок ли», некоторые задачи на путях
Полный обход (запись при каждом возврате)2n−12n - 1LCA через RMQ

Во втором варианте tout[v] получает собственное время при выходе, и проверка предка становится tin[u] < tin[v] and tout[v] < tout[u]. Для отрезков поддеревьев он неудобен: в массиве оказываются «пустые» позиции выходов. Если сомневаетесь — берите первый вариант, он закрывает большинство задач.

Сложность

  • Построение tin, tout, order: O(n)O(n) времени и памяти — один DFS.
  • Проверка «предок ли»: O(1)O(1).
  • Запрос и обновление на поддереве через Фенвик или дерево отрезков: O(log⁡n)O(\log n).
  • LCA через полный обход и sparse table: O(nlog⁡n)O(n \log n) предподсчёт, O(1)O(1) запрос.

Типичные ошибки

  1. Путают вершину и её позицию. В Фенвик кладётся values[v] по индексу tin[v], а если нужно восстановить вершину по позиции — order[i]. Помогает дисциплина в именах: v для вершин, i или pos для позиций.
  2. tout на единицу больше. Если писать tout[v] = timer после цикла (а не timer - 1), получится полуинтервал [tin, tout). Это тоже рабочий вариант, но смешивать его с закрытыми отрезками в запросах нельзя — выберите один и придерживайтесь его.
  3. Рекурсия на Python. Бамбук из 10510^5 вершин — стандартный тест. Пишите итеративный DFS.
  4. Не тот корень. Если в условии дерево задано рёбрами без корня, а запросы про «поддерево», корень обычно указан явно (часто вершина 1 при нумерации с единицы). Обход от другого корня даст другие поддеревья.
  5. Разные обходы для разных структур. Если строить tin в одном месте программы, а потом ещё раз в другом с другим порядком соседей, отрезки перестанут совпадать. Посчитайте один раз и передавайте.

Где встречается на собеседованиях

Сама формулировка «Эйлеров обход» на интервью звучит редко, зато задачи, где он — самое чистое решение, встречаются:

  • «Является ли A руководителем B» в оргструктуре компании, много запросов. Это ровно is_ancestor. Наивное «поднимаемся по начальникам» — хороший старт, предподсчёт tin/tout — ожидаемое улучшение.
  • Сумма/количество в поддереве с изменениями: зарплатный фонд отдела, число активных файлов в папке файловой системы, количество комментариев в ветке обсуждения.
  • LCA — тут Эйлеров обход идёт как один из способов наряду с двоичными подъёмами.
  • Олимпиадные задачи: «количество различных цветов в поддереве» (линеаризация плюс офлайн-обработка запросов-отрезков, например алгоритмом Мо), «k-й по величине элемент поддерева», прибавление на поддереве.

Хорошая подача на интервью: сначала проговорить, что поддерево после DFS — непрерывный отрезок, и объяснить почему. Дальше задача сводится к «известной структуре на массиве», и интервьюер это сразу оценит.

Итог

Эйлеров обход дерева — это DFS с таймером, который превращает дерево в массив. Поддерево становится отрезком [tin[v], tout[v]], проверка предка — двумя сравнениями, а вся мощь Фенвика и дерева отрезков становится доступна для деревьев. Если в задаче есть слово «поддерево» и много запросов — почти наверняка начинать стоит с tin и tout.

Чтобы закрепить базу, полезно повторить обходы в глубину и ширину и динамику на деревьях: многие задачи на поддеревья без обновлений решаются одним DFS, и линеаризация там не нужна.

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

Все задачи