Дерево — это граф, состоящий из n вершин и ровно n - 1 ребер; этот граф должен удовлетворять следующему условию: существует ровно один кратчайший (по количеству ребер) путь между любой парой его вершин.
Поддерево дерева T — это дерево, где как вершины, так и ребра являются подмножествами вершин и ребер T.
Вам дано дерево с n вершинами. Вы можете считать, что его вершины пронумерованы целыми числами от 1 до n. Дополнительно в каждой вершине дерева записано целое число. Изначально целое число, записанное в i-ой вершине, равняется vi. За один ход Вы можете применить следующую операцию:
- Выбрать поддерево данного дерева, которое включает вершину с номером 1.
- Увеличить (или уменьшить) на один все целые числа, записанные в вершинах этого поддерева.
Вычислите минимальное количество ходов, необходимое для того, чтобы сделать все целые числа, записанные в вершинах данного дерева, равными нулю.
Выходные данные
Выведите минимальное количество операций, необходимое для решения задачи.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2
1 3
1 -1 1
|
3
|