Codeforces Round 800 (Div. 1) |
---|
Закончено |
Нам дано корневое дерево, состоящее из $$$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)$$$.
За одну операцию мы делаем следующее:
Какое минимальное количество операций необходимо для достижения нашей цели?
Первая строка содержит целое число $$$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$$$.
Для каждого набора входных данных выведите минимально необходимое количество операций.
4211 52 931 14 52 46 1041 2 16 95 64 52 451 2 3 45 54 43 32 21 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$$$.
Название |
---|