P5992 [PA 2015] Rozstaw szyn

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.

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 one integer, the minimum possible sum of the absolute differences of weights between adjacent nodes in the tree.

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