Competitions

# DFS Applications

# Maximum sum on a tree

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

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._{i}

#### Input

First line contains the number of vertices **n** (**1** ≤ **n** ≤ `10`

) in a tree. Each of the next ^{5}**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`

- the number of coins in tree nodes. _{n}

#### Output

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

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