Spring Cleaning Tree

Flóra found a dusty tree map under the carpet – a tree with $N$ nodes (numbered from $1$ to $N$) and $N-1$ edges. In the cleaning process, Flóra’s mother repeatedly chooses two leaf nodes (a leaf is defined as a node with exactly one adjacent node) and cleans every edge on the unique path between them. If the path has $d$ edges, the cleaning cost of that operation is $d$. However, each leaf node can be chosen at most once as an endpoint for a cleaning operation. The cleaning process stops when every edge in the tree has been cleaned at least once, and the total cleaning cost is the sum of the costs of all cleaning operations.

Flóra, wanting to make the tree more interesting, performs modifications on the original tree. In the $i$-th modification, she adds $D_i$ new leaf nodes. Specifically, she chooses a node in the original tree and attaches a new leaf node to it by a new edge. (Note that when new leaves are attached, some nodes that were leaves in the original tree may no longer be leaves.)

Your task is to help Flóra determine the minimum total cleaning cost for the modified tree.

Observation: With optimal choices of attachment points, it is always possible to decompose the edge set of the final tree into a collection of paths whose endpoints are leaves (and each leaf is used at most once). In such a decomposition every edge is cleaned exactly once, so the minimum total cost equals the total number of edges in the final tree.

The final tree consists of the original $N-1$ edges plus all the new edges added during modifications. Hence, if $R = \sum_{i=1}^{Q}D_i$, then the answer is

$$\text{Answer} = (N-1) + \Bigl( \sum_{i=1}^{Q} D_i \Bigr). $$

inputFormat

The first line contains two integers $N$ and $Q$, where $N$ is the number of nodes in the original tree and $Q$ is the number of modifications.

The next $N-1$ lines each contain two integers $u$ and $v$, representing an edge connecting nodes $u$ and $v$.

The following $Q$ lines each contain a single integer $D_i$, indicating that in the $i$-th modification, $D_i$ new leaf nodes are added (each connected by a new edge to a node you may choose optimally).

You may assume that the input is valid and that the tree is connected.

outputFormat

Output a single integer, the minimum total cleaning cost for the modified tree.

Explanation: Since the optimal cleaning strategy cleans each edge exactly once, and the final tree has \((N-1) + \sum_{i=1}^{Q} D_i\) edges, the answer is exactly \((N-1) + \sum_{i=1}^{Q} D_i\).

sample

3 1
1 2
2 3
1

3