Two Trees

You are given two trees, each with $N$ vertices. In both trees the vertices are numbered $0$ through $N-1$, and the same number refers to the same vertex.

Vertex $i$ has score $S_i$.

Choose a subset of $\{0, 1, \dots, N-1\}$ that satisfies both of these conditions.

• Keeping only the chosen vertices in the first tree leaves a connected subgraph.
• Keeping only the chosen vertices in the second tree leaves a connected subgraph.

Write a program that finds the largest sum of scores over all such subsets. The empty subset is allowed and its sum is $0$, so the answer is never negative.

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 the first tree, given as the numbers of the two vertices it joins.

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

The last line contains the scores $S_0, S_1, \dots, S_{N-1}$ separated by spaces ($-1000 \le S_i \le 1000$).

Print the largest sum of scores on the first line.

In the first example, $\{0, 1\}$ forms a connected subgraph in both trees. $\{0, 1, 2\}$ does not. In the second tree vertex $2$ is joined only to vertex $3$, and vertex $3$ is not in the set.