B. Фейковые пластиковые деревья
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нам дано корневое дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Корнем дерева является вершина $$$1$$$, а родителем вершины $$$v$$$ является $$$p_v$$$.

В каждой вершине записано число, изначально все числа равны $$$0$$$. Обозначим число, записанное в вершине $$$v$$$, как $$$a_v$$$.

Для каждой $$$v$$$ мы хотим, чтобы $$$a_v$$$ находилось между $$$l_v$$$ и $$$r_v$$$ $$$(l_v \leq a_v \leq r_v)$$$.

За одну операцию мы делаем следующее:

  • Выбираем некоторую вершину $$$v$$$. Пусть $$$b_1, b_2, \ldots, b_k$$$  — вершины на пути от вершины $$$1$$$ до вершины $$$v$$$ (то есть $$$b_1 = 1$$$, $$$b_k = v$$$ и $$$b_i = p_{b_{i + 1}}$$$).
  • Выберем неубывающий массив $$$c$$$ длины $$$k$$$ из неотрицательных целых чисел: $$$0 \leq c_1 \leq c_2 \leq \ldots \leq c_k$$$.
  • Для каждого $$$i$$$ $$$(1 \leq i \leq k)$$$, увеличим $$$a_{b_i}$$$ на $$$c_i$$$.

Какое минимальное количество операций необходимо для достижения нашей цели?

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

Первая строка содержит целое число $$$t$$$ $$$(1\le t\le 1000)$$$  — количество наборов входных данных. Далее следует описание наборов входных данныхв.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(2\le n\le 2 \cdot 10^5)$$$  — количество вершин в дереве.

Вторая строка каждого набора входных данных содержит $$$n - 1$$$ целых чисел, $$$p_2, p_3, \ldots, p_n$$$ $$$(1 \leq p_i < i)$$$, где $$$p_i$$$ обозначает родителя вершины $$$i$$$.

В $$$i$$$-й из следующих $$$n$$$ строк содержится два целых числа $$$l_i$$$ и $$$r_i$$$ $$$(1 \le l_i \le r_i \le 10^9)$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимально необходимое количество операций.

Пример
Входные данные
4
2
1
1 5
2 9
3
1 1
4 5
2 4
6 10
4
1 2 1
6 9
5 6
4 5
2 4
5
1 2 3 4
5 5
4 4
3 3
2 2
1 1
Выходные данные
1
2
2
5
Примечание

В первом наборе входных данных мы можем достичь цели с помощью одной операции: выбрать $$$v = 2$$$ и $$$c = [1, 2]$$$, в результате чего $$$a_1 = 1, a_2 = 2$$$.

Во втором наборе входных данных мы можем достичь цели с помощью двух операций: сначала выбираем $$$v = 2$$$ и $$$c = [3, 3]$$$, в результате чего $$$a_1 = 3, a_2 = 3, a_3 = 0$$$. Затем выбираем $$$v = 3, c = [2, 7]$$$, в результате $$$a_1 = 5, a_2 = 3, a_3 = 7$$$.