Олимпиадный тренинг

Задача . E. Прекрасное дерево!

Задача

Темы: Деревья жадные алгоритмы Перебор поиск в глубину и подобное снм Структуры данных *2000

Да благословят боги этот прекрасный ArrayForces!

Случайная галька

Дано дерево с $n$ вершинами с корнем в вершине $1$, в $i$-й вершине записано целое число $a_i$.

Пусть $L$ — это множество всех прямых сыновей$^{\text{∗}}$ вершины $v$. Назовём дерево прекрасным, если для всех вершин $v$ с непустым $L$ верно a_v \le \sum_{u \in L}{a_u}.

За одну операцию вы можете выбрать любую вершину $v$ и увеличить значение $a_v$ на $1$.

Найдите минимальное количество операций, необходимых для того, чтобы сделать данное дерево прекрасным!

$^{\text{∗}}$ Вершина $u$ называется прямым сыном $v$, если:

$u$ и $v$ соединены ребром, и
$v$ лежит на (единственном) пути от $u$ до корня дерева.

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

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

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

Вторая строка каждого набора входных данных содержит $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — значения, написанные на вершинах дерева.

Третья строка каждого набора входных данных содержит $n - 1$ целых чисел $p_2, p_3 , \ldots, p_n$ ($1 \le p_i < i$), каждое из которых означает, что в графе есть ребро между вершинами $i$ и $p_i$. Гарантируется, что данные ребра образуют дерево.

Гарантируется, что сумма $n$ по всем наборам входных данных не превышает $5000$.

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

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

Примечание

Дерево в первом наборе входных данных:

$\text{[math]}$ Вы можете применить операцию к вершине $5$ и дважды к вершине $2$, чтобы получить прекрасное дерево.

Во втором наборе входных данных вы можете два раза применить операцию к вершине $2$, чтобы получить прекрасное дерево.

В третьих и четвёртых наборах входных данных дерево уже прекрасно, поэтому применять операций не надо.

Примеры

№	Входные данные	Выходные данные
1	4 5 9 3 4 1 2 1 1 3 3 2 5 3 1 2 36 54 1 3 0 0 0 1 2	3 2 0 0

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам

	Кол-во
С++ Mingw-w64	3

Комментарий учителя

Ваш ответ

выберите язык и введите исходный код

Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!

Загруженные файлы

Нет