Задачі
Максимальна сума на дереві
Максимальна сума на дереві
Є дерево із n вершин, де вершина номер i~(1 \le i \le n) має c_i монет. Вам слід обрати таку підмножину вершин, в якій ніякі дві з них не є сусідніми (тобто вершини об’єднані ребром), а сума монет у вибраних вершинах найбільша.
Вхідні дані
Перший рядок містить кількість вершин n~(1 \le n \le 10^5) в дереві. Кожен з наступних n - 1 рядків містить два числа u і v~(1 \le u, v \le n), які задають ребро в дереві. Останній рядок містить n цілих невід’ємних чисел c_1, ... c_n — кількість монет у вершинах дерева.
Вихідні дані
Виведіть максимально можливу суму монет у вибраній підмножині вершин дерева.
Приклад
Вхідні дані #1
5 1 2 1 3 2 4 2 5 1 5 7 1 2
Вихідні дані #1
12
Вхідні дані #2
5 1 2 1 3 2 4 2 5 3 7 5 10 1
Вихідні дані #2
16