Обходы бинарного дерева

Бинарное дерево – это набор вершин, у каждой из которых может быть левый и правый ребёнок. Одна из вершин является корнем дерева, она не является ребёнком какой-то другой. Начав в корне и каждый раз переходя в одного из детей, можно дойти до любой вершины. Множество вершин, до которых можно дойти из заданной, называется её поддеревом.

У бинарного дерева есть три основных обхода: прямой (pre-order), центрированный (in-order) и обратный (post-order).

Прямой обход дерева – это порядок его вершин, полученный следующим рекурсивным алгоритмом:

1. Добавить корень дерева в обход.
2. Если у корня есть левый ребёнок, выписать прямой обход его поддерева.
3. Если у корня есть правый ребёнок, выписать прямой обход его поддерева.

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

Обобщим эти три варианта обхода: пусть в каждой вершине записано целое число x от −1 до 1, обозначающее, в какой момент мы выписываем эту вершину, а именно:

• x = −1: до обходов поддеревьев её детей;
• x = 0: между обходами поддеревьев её детей;
• x = 1: после обходов поддеревьев её детей.

Таким образом, если во всех вершинах записано −1, обход является прямым, если 0 – центрированным, если 1 – обратным.

Рассмотрим дерево с n вершинами, пронумерованных от 1 до n. Корень дерева – вершина 1. Изначально во всех вершинах записано число −1.

В рамках исследования необходимо обработать q запросов одного из следующих типов:

1. Поменять числа в вершинах l, l+1, ..., r на x (x равен −1, 0 или 1).
2. Сообщить, на какой позиции в текущем обходе будет стоять вершина i.

Необходимо вывести ответы на все запросы второго типа.

Входные данные

В первой строке входного файла INPUT.TXT заданы два целых числа n и q (1 ≤ n, q ≤ 100 000).

В следующих n строках даны по два целых числа L_i и R_i (0 ≤ L_i, R_i ≤ n) – номер левого и правого ребёнка вершины i соответственно, либо 0, если соответствующий ребёнок отсутствует.

Гарантируется, что L_i и R_i задают корректное бинарное дерево.

В следующих q строках даны запросы. Первое число в строке t (t ∈ {1, 2}) – тип запроса.

В случае запроса первого типа далее даны целые числа l, r и x (1 ≤ l ≤ r ≤ n, x равен −1, 0 или 1) – границы отрезка вершин, в которых меняются числа, и новое значение.

В случае запроса второго типа далее дано число i (1 ≤ i ≤ n) – номер вершины, позицию которой в обходе необходимо вывести.

Выходные данные

На каждый запрос второго типа в выходной файл OUTPUT.TXT в отдельной строке выведите единственное число от 1 до n – позицию соответствующей вершины в обходе.

Пример

Замечание

В примере граф имеет следующий вид:

Обход графа меняется следующим образом:

• [1, 3, 5, 2, 4]
• [5, 2, 3, 4, 1]
• [5, 3, 2, 4, 1]

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]