Sum of Scores

You are given two trees $A$ and $B$, each with $N$ vertices. In both trees the vertices are numbered 0 to $N-1$, and vertex $i$ has score $s_i$. Scores are integers and may be negative.

Choose a non-empty subset $S \subseteq \{0, 1, \dots, N-1\}$ that satisfies both conditions below.

• Keeping only the vertices of $S$ in tree $A$ leaves a connected subgraph.
• Keeping only the vertices of $S$ in tree $B$ leaves a connected subgraph.

Among all such subsets $S$, find the maximum value of the score sum $\sum_{i \in S} s_i$.

The first line contains the number of vertices $N$. ($2 \le N \le 50$)

Each of the next $N-1$ lines contains one edge of tree $A$ as two integers $a$ and $b$. ($0 \le a, b \le N-1$, $a \ne b$)

Each of the following $N-1$ lines contains one edge of tree $B$ in the same format.

The last line contains $N$ integers $s_0, s_1, \dots, s_{N-1}$ separated by spaces. ($-1000 \le s_i \le 1000$)

Both graphs in the input are trees.

Print the maximum score sum on the first line.

In the first example the score sum is largest for $\{0, 1\}$. Picking $\{0, 1, 2\}$ does not leave a connected subgraph in tree $B$.