tree-algorithms

Задача A. LCA

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 5 секунд
Ограничение по памяти: 256 мегабайт

Дано подвешенное дерево с корнем в первой вершине. Вам нужно ответить на m запросов вида "найти LCA двух вершин".

LCA вершин u и v в подвешенном дереве — это наиболее удалённая от корня дерева вершина, лежащая на обоих путях отuиvдо корня.

Формат входных данных

В первой строке задано целое число n — число вершин в дереве (1 ⩽ n ⩽ 2 * 10⁵).

В следующих n - 1 строках записано одно целое число x. Число x на строке i означает, что x — предок вершины i (x < i).

Затем дано число m.

Далее заданы m (0 ⩽ m ⩽ 5 * 10⁵) запросов вида (u, v) — найти LCA двух вершин u и v (1 ⩽ u, v ⩽ n, u ⩽ v).

Формат выходных данных

Для каждого запроса выведите LCA двух вершин на отдельной строке.

Примеры

стандартный ввод

5 1 1 2 3 2

стандартный вывод

2 3
4 5
1 1 5 1 1 2 2 3
4 5
4 2
3 5
2
2
1

Задача B. Самое дешевое ребро

Имя входного файла: minonpath.in
Имя выходного файла: minonpath.out
Ограничение по времени: 4 секунды
Ограничение по памяти: 256 мегабайт

Дано подвешенное дерево с корнем в первой вершине. Все ребра имеют веса (стоимости). Вам нужно ответить на M запросов вида "найти у двух вершин минимум среди стоимостей ребер пути между ними".

Формат входных данных

В первой строке задано целое число n — число вершин в дереве (1 ⩽ n ⩽ 2 * 10⁵). В следующих n - 1 строках записаны два целых числа x и y. Число x на строке i означает, что x — предок вершины i, yзадает стоимость ребра (x < i, |y|⩽ 10⁶).

Далее заданы m (0 ⩽ m ⩽ 5 * 10⁵) запросов вида (x, y) — найти минимум на пути из x в y (1 ⩽ x, y ⩽ n, x ⩽ y).

Формат выходных данных

Выведите ответы на запросы.

Примеры

minonpath.in

5
1 2
1 3
2 5
3 2
2
2 3
4 5

minonpath.out

2
2
5
1 1
1 2
2 3
3 4
2
1 4
3 2
1
1

Задача F. Опекуны карнотавров

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 64 мегабайта

Карнотавры очень внимательно относятся к заботе о своем потомстве. У каждого динозавра обязательно есть старший динозавр, который его опекает. В случае, если опекуна съедают (к сожалению, в юрский период такое не было редкостью), забота о его подопечных ложится на плечи того, кто опекал съеденного динамозавра. Карнотавры — смертоносные хищники, поэтому их обычаи строго запрещают им драться между собой. Если у них возникает какой-то конфликт, то, чтобы решить его, они обращаются к кому-то из старших, которому доверяют, а доверяют они только тем, кто является их опекуном или опекуном их опекуна и так далее (назовем таких динозавров суперопекунами). Поэтому для того, чтобы решить спор двух карнотавров, нужно найти такого динозавра, который является суперопекуном для них обоих. Разумеется, беспокоить старших по пустякам не стоит, поэтому спорщики стараются найти самого младшего из динозавров, который удовлетворяет этому условию. Если у динозавра возник конфликт с его суперопекуном, то этот суперопекун сам решит проблему. Если у динозавра нелады с самим собой, он должен разобраться с этим самостоятельно, не беспокоя старших. Помогите динозаврам разрешить их споры.

Формат входных данных

Во входном файле записано число M , обозначающее количество запросов (1 ⩽ M ⩽ 200000).

Далее на отдельных строках следуют M запросов, обозначающих следующие события:

• + v — родился новый динозавр и опекунство над ним взял динозавр с номеромv. Родившемуся динозавру нужно присвоить наименьший натуральный номер, который до этого еще никогда не встречался.
• - v — динозавра номерvсъели
• ? u v — у динозавров с номерамиuиvвозник конфликт и вам надо найти им третейского судью.

Изначально есть один прадинозавр номер 1, гарантируется, что он никогда не будет съеден.

Формат выходных данных

Для каждого запроса типа «?» в выходной файл нужно вывести на отдельной строке одно число — номер самого молодого динозавра, который может выступить в роли третейского судьи.

Пример

стандартный ввод

11
+ 1
+ 1
+ 2
? 2 3
? 1 3
? 2 4
+ 4
+ 4
- 4
? 5 6
?

стандартный вывод

1
1
2
2
5

Задача H. Дерево

Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Задано подвешенное дерево, содержащее n (1 ⩽ n ⩽ 1 000 000) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество различных цветов, встречающихся в поддереве с корнем v.

Формат входных данных

В первой строке входного файла задано число n. Последующиеnстрок описывают вершины, по одной в строке. Описание очередной вершины i имеет вид p_i c_i, где p_i — номер родителя вершины i, а c_i — цвет вершины i (1 ⩽ c_i ⩽ n). Для корня дерева p_i = 0.

Формат выходных данных

Выведите n чисел, обозначающих количества различных цветов в поддеревьях с корнями в вершинах 1..n.

Пример

стандартный ввод

5
2 1
3 2
0 3
3 3
2 1

стандартный вывод

1 2 3 1 1