Competitions

# Dynamic programming on Trees - Top Level

# Maximum sum on a tree

Given a tree of n nodes, where each node i (1 ≤ i ≤ n) has `c[i]`

coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes (i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.

## Input data

The first line contains the number of vertices n (1 ≤ n ≤ `10^5`

) in a tree. Each of the next n - 1 lines gives two integers u and v (1 ≤ u, v ≤ n) and describes an edge in a tree. The last line contains n positive integers `c[1]`

, ... `c[n]`

- the number of coins in tree nodes.

## Output data

Print the maximum sum of coins in a chosen subset of tree nodes.

## Examples

Input example #1

5 1 2 1 3 2 4 2 5 1 5 7 1 2

Output example #1

12

Input example #2

5 1 2 1 3 2 4 2 5 3 7 5 10 1

Output example #2

16