2025/26, Кружок для начинающих, LCA
A: Предок_0
Напишите программу, которая для двух вершин дерева определяет, является ли одна из них предком другой.
Формат входных данных
Первая строка входного файла содержит натуральное число \(n\) (\(1 \le n \le 100\,000\)) — количество вершин в дереве. Во второй строке находятся \(n\) чисел, \(i\)-е из которых определяет номер непосредственного родителя вершины с номером
\(i\). Если это число равно нулю, то вершина является корнем дерева.
В третьей строке находится число \(m\) (\(1 \le m \le 100\,000\)) — количество запросов. Каждая из следующих \(m\) строк содержит два различных числа \(a\) и \(b\) (\(1 \le a, b \le n\)).
Формат выходных данных
Для каждого из \(m\) запросов выведите на отдельной строке число 1, если вершина \(a\) является одним из предков вершины \(b\), и 0 в противном случае.
Пример
| Ввод | Вывод |
|---|
6
0 1 1 2 3 3
5
4 1
1 4
3 6
2 6
6 5
|
0
1
1
0
0
|
B: LCA
Задано подвешенное дерево, содержащее \(n\) (\(1 \leq n \leq 100\,000\)) вершин, пронумерованных от \(0\) до \(n - 1\). Требуется ответить на \(m\) (\(1 \leq m \leq 100\,000\)) запросов о наименьшем общем предке для пары вершин.
Запросы генерируются следующим образом. Заданы числа \(a_1\), \(a_2\) и числа \(x\), \(y\) и \(z\). Числа \(a_3, \dots, a_{2m}\) генерируются следующим образом: \(a_i = (x \cdot a_{i - 2} + y \cdot a_{i - 1} + z) \bmod n\). Первый запрос имеет вид \((a_1, a_2)\). Если ответ на \((i - 1)\)-й запрос равен \(v\), то \(i\)-й запрос имеет вид \(((a_{2i - 1} + v) \bmod n, a_{2i})\).
Формат входных данных
Первая строка содержит два числа: \(n\) и \(m\). Корень дерева имеет номер \(0\). Вторая строка содержит \(n - 1\) целых чисел, \(i\)-е из этих чисел равно номеру родителя вершины \(i\). Третья строка содержит два целых числа в диапазоне от \(0\) до \(n - 1\): \(a_1\) и \(a_2\). Четвертая строка содержит три целых числа: \(x\), \(y\) и \(z\), эти числа неотрицательны и не превосходят \(10^9\).
Формат выходных данных
Выведите в выходной файл сумму номеров вершин — ответов на все запросы.
Примеры
| Ввод | Вывод |
|---|
3 2
0 1
2 1
1 1 0
|
2
|
1 2
0 0
1 1 1
|
0
|
C: Dynamic LCA
Постановка задачи о Наименьшем общем предке такова: дано дерево \(T\) с выделенным корнем и две вершины \(u\) и \(v\), \(lca(u, v)\) — вершина с максимальной глубиной, которая является предком и \(u\), и \(v\). Например, в картинке внизу \(lca(8, 7)\) — вершина \(3\).
С помощью операции \(chroot(u)\) мы можем менять корень дерева, достаточно отметить \(u\), как новый корень, и направить ребра вдоль пути от корня. Наименьшие общие предки вершин поменяются соответствующе. Например, если мы сделаем \(chroot(6)\) на картинке сверху, \(lca(8, 7)\) станет вершина \(6\). Получившееся дерево изображено снизу.
Вам дано дерево \(T\). Изначально корень этого дерева — вершина \(1\). Напишите программу, которая поддерживает эти две операции: \(lca(u, v)\) и \(chroot(u)\).
Формат входных данных
Входной файл состоит из нескольких тестов.
Первая строка каждого теста содержит натуральное число \(n\) — количество вершин в дереве (\(1 \leq n \leq 100\,000\)). Следующие \(n - 1\) строки содержат по \(2\) натуральных числа и описывают ребра дерева. Далее идет строка с единственным натуральным числом \(m\) — число операций. Следующие \(m\) строк содержат операции. Строка "? \(u\) \(v\)" означает операцию \(lca(u, v)\), a строка "! \(u\)" — \(chroot(u)\). Последняя строка содержит число \(0\).
Сумма \(n\) для всех тестов не превосходит \(100\,000\). Сумма \(m\) для всех тестов не превосходит \(200\,000\).
Формат выходных данных
Для каждой операции "? \(u\) \(v\)" выведите значение \(lca(u, v)\). Числа разделяйте переводами строк.
Пример
| Ввод | Вывод |
|---|
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
10
? 4 5
? 5 6
? 8 7
! 6
? 8 7
? 4 5
? 4 7
? 5 9
! 2
? 4 3
0
|
2
1
3
6
2
3
6
2
|
D: Чип и Дейл в лабиринте
Чип и Дейл спешат на помощь! Но внимательные зрители знают, что помощь как правило нужна самим Чипу и Дейлу, поэтому сегодня вам надо будет сыграть роль сообразительной Гаечки. Итак, Чип и Дейл снова попали в лапы к Толстопузу. Кот очень не любит
грызунов и поэтому приготовил им изощренное испытание. Он собирается поместить их в лабиринт и посмотреть смогут ли они из него выбраться. Лабиринт представляет собой дерево, в котором каждое ребро имеет одно направление. Гаечка подслушала
разговор Толстопузу со своими сообщниками и теперь знает несколько возможных вариантов: в какую точку лабиринта поместят её друзей, и где будет выход. Для каждого такого варианта она хочет понять, смогут ли Чип и Дейл найти выход, или нет.
Формат входных данных
В первой строке записано число \(n\) (\(n \leq 10^5\)) - количество вершин дерева. В следующих \(n-1\) строках описаны ребра дерева. В \(i+1\)-ой строке записано номера вершин \(a_i, b_i\), означающие, что в дереве есть ребро из вершины \(a_i\)
в вершину \(b_i\).
Далее на отдельной строке записано число \(m\) (\(m \leq 10^5\)) -- количество запросов. После этого идут \(m\) строк с описанием запросов, в \(n + 1 + i\)-ой строке записаны через пробел числа \(x_i\) и \(y_i\).
Формат выходных данных
Для каждого запроса на отдельной строке требуется вывести Yes, если в графе есть путь между вершинами \(x_i\) и \(y_i\), и No иначе.
Примеры
| Ввод | Вывод |
|---|
4
1 2
3 1
4 1
6
1 2
3 2
2 3
4 2
4 3
2 1
|
Yes
Yes
No
Yes
No
No
|
4
1 2
3 2
3 4
6
1 2
1 3
1 4
2 3
2 4
3 4
|
Yes
No
No
No
No
Yes
|
E: RMQ
Реализуйте структуру данных, которая на данном массиве из \(N\) целых чисел позволяет узнать максимальное значение на отрезке.
Формат входных данных
В первой строке вводится натуральное число \(N\) \((1 \leq N \leq 10^5)\) – количество элементов в массиве. В следующей строке содержатся \(N\) целых чисел, не превосходящих по модулю
10^9 – элементы массива. Далее идет число \(K\) \((0 \leq K \leq 10^5)\) – количество запросов к структуре данных. Каждая из следующих \(K\) строк содержит два целых числа \(l\) и \(r\) \((1 \leq l \leq r \leq N)\) – левую и правую границы отрезка в массиве для данного запроса.
Формат выходных данных
Для каждого из запросов выведите два числа: наибольшее значение среди элементов массива на отрезке от \(l\) до \(r\).
Примеры
| Ввод | Вывод |
|---|
5
7 3 1 6 4
3
1 5
2 4
3 3
|
7
6
1
|
1
0
1
1 1
|
0
|