eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дерево в отрезке

Дерево в отрезке

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Задано подвешенное дерево, содержащее n (1n300000) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество вершин с цветами в m (1m10) отрезках-запросах l[i], r[i], встречающихся в поддереве с корнем v. Вершина лежит в отрезке, если номер её цвета c (l[i]cr[i]).

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

В первой строке задано числа n и m. Последующие n строк описывают вершины, по одной в строке. Описание очередной вершины i имеет вид p[i]c[i], где p[i] - номер родителя вершины i, а c[i] - цвет вершины i (1c[i]n). Для корня дерева p[i] = 0.

Следующие m строк содержат запросы в формате двух чисел l[i], r[i] (1l[i]r[i]n).

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

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

Пример

Входные данные #1
5 2
2 1
3 2
0 3
3 3
2 1
1 5
2 3
Выходные данные #1
1 0
3 1
5 3
1 1
1 0
Входные данные #2
1 1
0 1
1 1
Выходные данные #2
1
Входные данные #3
2 1
0 1
1 1
1 1
Выходные данные #3
2
1
Входные данные #4
2 3
0 1
1 2
1 1
2 2
1 2
Выходные данные #4
1 1 2
0 1 1