Да благословят боги этот прекрасный ArrayForces!
Случайная галька
Дано дерево с \(n\) вершинами с корнем в вершине \(1\), в \(i\)-й вершине записано целое число \(a_i\).
Пусть \(L\) — это множество всех прямых сыновей\(^{\text{∗}}\) вершины \(v\). Назовём дерево прекрасным, если для всех вершин \(v\) с непустым \(L\) верно \(\)a_v \le \sum_{u \in L}{a_u}.\(\)
За одну операцию вы можете выбрать любую вершину \(v\) и увеличить значение \(a_v\) на \(1\).
Найдите минимальное количество операций, необходимых для того, чтобы сделать данное дерево прекрасным!
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество операций, необходимых для того, чтобы сделать данное дерево прекрасным!
Примечание
Дерево в первом наборе входных данных:
Вы можете применить операцию к вершине
\(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
|