题目描述

题目译自 PA 2015 Runda 3 Rozstaw szyn

在某些方面，拜托西亚是一个相当落后的国家：尽管周边国家早已拥有铁路，拜托西亚仍然没有铁路系统。这种情况必须改变！

Bajtazar 是新成立的拜托克国家铁路公司的首席工程师，他设计了一个铁路网络。该网络连接了拜托西亚境内的若干车站以及境外的若干车站。每条铁路连接在两个车站之间运行，并且是双向的。从网络中的任意车站到其他任意车站有且仅有一条路径，且途中不会重复经过任何车站。

然而，问题复杂化了，因为每个邻国都采用了自己的轨道间距标准。并且，无法在拜托西亚境外的任何车站更改轨道间距。因此，工程师 Bajtazar 决定如下：拜托西亚不会采用统一的轨道间距标准——境内每个车站的轨道间距可以不同。而在连接车站的铁路上，将安装 BAZRK 系统（拜托克自动轮距调整系统），允许列车在行驶中改变轮距。

当然，BAZRK 系统是一种相当昂贵的解决方案；如果两个相连车站的轨道间距分别为 $r_{1}$ 和 $r_{2}$ 比特米（bitometr），则在它们之间的轨道上安装 BAZRK 系统的成本为 $|r_{1} - r_{2}|$ 兆拜塔拉尔（megabajtalar）。

请帮助 Bajtazar 为拜托西亚境内的每个车站选择轨道间距，以最小化 BAZRK 系统的总成本。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(2 \leq n \leq 500000, 1 \leq m \leq n)$，分别表示网络中车站的总数（包括拜托西亚境内和境外的车站）以及境外车站的数量。境外车站编号为 $1$ 到 $m$，境内车站编号为 $m+1$ 到 $n$。

接下来的 $n-1$ 行描述车站之间的铁路连接：第 $i$ 行包含两个整数 $u_{i}, v_{i}$ $(1 \leq u_{i}, v_{i} \leq n, u_{i} \neq v_{i})$，表示编号为 $u_{i}$ 和 $v_{i}$ 的车站之间存在直接铁路连接。每个境外车站仅与其他一个车站相连，而每个境内车站至少与其他两个车站相连。

接下来的 $m$ 行包含境外车站的轨道间距：第 $i$ 行包含一个整数 $r_{i}$ $(1 \leq r_{i} \leq 500000)$，表示编号为 $i$ 的境外车站的轨道间距（单位：比特米）。

输出格式

输出应为一行，包含一个整数，表示安装 BAZRK 系统的最小可能总成本（单位：兆拜塔拉尔），向下取整到最近的整数。

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

35