Дерево у відрізку
Дерево у відрізку
Задано підвішене дерево, яке містить n (1 ≤ n ≤ 300000) вершин. Кожну з вершин пофарбовано в один з n кольорів. Потрібно для кожної вершини v обчислити кількість вершин з кольорами в m (1 ≤ m ≤ 10) відрізках-запитах li
, ri
, які зустрічаються у піддереві з коренем v. Вершина лежить у відрізку, якщо номер її кольору c (li
≤ c ≤ ri
).
Вхідні дані
У першому рядку задано числа n та m. Наступні n рядків, які описують вершини, по одній у рядку. Опис чергової вершини i
має вид pi
ci
, де pi
- номер батька вершини i, а ci
- колір вершини i (1 ≤ ci
≤ n). Для кореня дерева pi
= 0.
Наступні m рядків містять запити у форматі двох чисел li
, ri
(1 ≤ li
≤ ri
≤ n).
Вихідні дані
Виведіть 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