Дерево в отрезке
Дерево в отрезке
Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 300000) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество вершин с цветами в m (1 ≤ m ≤ 10) отрезках-запросах li
, ri
, встречающихся в поддереве с корнем v. Вершина лежит в отрезке, если номер её цвета c (li
≤ c ≤ ri
).
Input
В первой строке задано числа n и m. Последующие n строк описывают вершины, по одной в строке. Описание очередной вершины i имеет вид pi
ci
, где pi
- номер родителя вершины i, а ci
- цвет вершины i (1 ≤ ci
≤ n). Для корня дерева pi
= 0.
Следующие m строк содержат запросы в формате двух чисел li
, ri
(1 ≤ li
≤ ri
≤ n).
Output
Выведите n строк по m чисел, обозначающих количества цветов в поддеревьях с корнями в вершинах 1, ..., n в соответствующих отрезках.
5 2 2 1 3 2 0 3 3 3 2 1 1 5 2 3
1 0 3 1 5 3 1 1 1 0
1 1 0 1 1 1
1
2 1 0 1 1 1 1 1
2 1
2 3 0 1 1 2 1 1 2 2 1 2
1 1 2 0 1 1