Description

Given a tree with $n$ nodes and $m$ leaf nodes, where the $m$ leaf nodes are nodes $1$ to $m$. Each leaf node has a weight $r_i$.

You need to assign a weight to each of the remaining $n-m$ nodes so that the sum of the absolute differences of weights between every pair of adjacent nodes in the tree is minimized.

Input Format

The first line contains two positive integers $n, m$, representing the number of nodes and the number of leaf nodes.

The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is an edge between $u$ and $v$.

The next $m$ lines each contain one positive integer, in order $r_1, r_2, \ldots, r_m$, representing the weight of each leaf.

Output Format

Output one integer, the minimum possible sum of the absolute differences of weights between adjacent nodes in the tree.

6 4
1 5
2 5
3 6
4 6
5 6
5
10
20
40

35

Hint

For $100\%$ of the testdata, $2 \le n \le 5 \times 10^5$, $1 \le m \le n$, $1 \le u, v \le n$, $1 \le r_i \le 5 \times 10^5$.

Translated by ChatGPT 5