B. Нулевое дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дерево — это граф, состоящий из n вершин и ровно n - 1 ребер; этот граф должен удовлетворять следующему условию: существует ровно один кратчайший (по количеству ребер) путь между любой парой его вершин.

Поддерево дерева T — это дерево, где как вершины, так и ребра являются подмножествами вершин и ребер T.

Вам дано дерево с n вершинами. Вы можете считать, что его вершины пронумерованы целыми числами от 1 до n. Дополнительно в каждой вершине дерева записано целое число. Изначально целое число, записанное в i-ой вершине, равняется vi. За один ход Вы можете применить следующую операцию:

  1. Выбрать поддерево данного дерева, которое включает вершину с номером 1.
  2. Увеличить (или уменьшить) на один все целые числа, записанные в вершинах этого поддерева.

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

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

Первая строка входных данных содержит n (1 ≤ n ≤ 105). Каждая из следующих n - 1 строк содержит два целых числа ai и bi (1 ≤ ai, bi ≤ n; ai ≠ bi), обозначающих, что существует ребро между вершинами ai и bi. Гарантируется, что граф, представленный во входных данных, является деревом.

Последняя строка входных данных содержит список из n целых чисел, записанных через пробел, v1, v2, ..., vn (|vi| ≤ 109).

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

Выведите минимальное количество операций, необходимое для решения задачи.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
3
1 2
1 3
1 -1 1
Выходные данные
3