3950. 树权

【题目描述】

给定一棵有 n 个点， m 个叶子节点的树，其中 m 个叶子节点分别为 1 到 m 号点，每个叶子节点有一个权值 ri。

你需要给剩下 n−m 个点各指定一个权值，使得树上相邻两个点的权值差的绝对值之和最小。

【输入格式】

第一行包含两个正整数 n,m，分别表示点数和叶子数。

接下来 n−1 行，每行两个正整数 u,v，表示 u 与 v 之间有一条边。

接下来 m 行，每行一个正整数，依次为 r1,r2,...,rm，表示每个叶子的权值。

【输出格式】

输出一个整数，即树上相邻两个点的权值差的绝对值之和的最小值。

【样例输入】

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

【样例输出】

35

【提示】

[数据范围]:

分值   数据范围

20%   n,r[i]<=2000

20%   n<=2000

20%   r[i]<=2000

40%   n,r[i]<=500000

数据随机。

【来源】