Дерево в отрезке
Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 300000) вершин. Каждая вершина покрашена в один из n цветов. Требуется для каждой вершины v вычислить количество вершин с цветами в m (1 ≤ m ≤ 10) отрезках-запросах l[i], r[i], встречающихся в поддереве с корнем v. Вершина лежит в отрезке, если номер её цвета c (l[i] ≤ c ≤ r[i]).
Входные данные
В первой строке задано числа n и m. Последующие n строк описывают вершины, по одной в строке. Описание очередной вершины i имеет вид p[i] c[i], где p[i] - номер родителя вершины i, а c[i] - цвет вершины i (1 ≤ c[i] ≤ n). Для корня дерева p[i] = 0.
Следующие m строк содержат запросы в формате двух чисел l[i], r[i] (1 ≤ l[i] ≤ r[i] ≤ n).
Выходные данные
Выведите n строк по m чисел, обозначающих количества цветов в поддеревьях с корнями в вершинах 1, ..., n в соответствующих отрезках.