[PA2015] Rozstaw szyn
题目描述
给定一棵有 $n$ 个点, $m$ 个叶子节点的树,其中 $m$ 个叶子节点分别为 $1$ 到 $m$ 号点,每个叶子节点有一个权值 $r_i$。
你需要给剩下 $n-m$ 个点各指定一个权值,使得树上相邻两个点的权值差的绝对值之和最小。
输入输出格式
输入格式
第一行包含两个正整数 $n,m$,分别表示点数和叶子数。
接下来 $n-1$ 行,每行两个正整数 $u,v$,表示 $u$ 与 $v$ 之间有一条边。
接下来 $m$ 行,每行一个正整数,依次为 $r_1,r_2,...,r_m$,表示每个叶子的权值。
输出格式
输出一个整数,即树上相邻两个点的权值差的绝对值之和的最小值。
输入输出样例
输入样例 #1
6 4
1 5
2 5
3 6
4 6
5 6
5
10
20
40
输出样例 #1
35
说明
对于 $100\%$ 的数据,$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$。