[PA2015]Rozstaw szyn

时间限制:10s      空间限制:128MB

题目描述

给定一棵有n个点,m个叶子节点的树,其中m个叶子节点分别为1到m号点,每个叶子节点有一个权值r[i]。你需要给剩下n-m个点各指定一个权值,使得树上相邻两个点的权值差的绝对值之和最小。


输入格式

第一行包含两个正整数n,m(2<=n<=500000,1<=m<=n),分别表示点数和叶子数。
接下来n-1行,每行两个正整数u,v(1<=u,v<=n),表示u与v之间有一条边。
接下来m行,每行一个正整数,依次为r[1],r[2],...,r[m](1<=r[i]<=500000),表示每个叶子的权值。


输出格式

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


样例输入

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

样例输出

35

提示

没有写明提示


题目来源

By Claris

Menuappsclose