Нам дано корневое дерево, состоящее из \(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\).
Какое минимальное количество операций необходимо для достижения нашей цели?
Выходные данные
Для каждого набора входных данных выведите минимально необходимое количество операций.
Примечание
В первом наборе входных данных мы можем достичь цели с помощью одной операции: выбрать \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|