ZYB 所在的城市可以被抽象为一棵N个点的树,每个点都是一个旅游景点,其中一号点是 ZYB 的家(当然 ZYB 的家也是个旅游景点了)。
某一天,ZYB 突然决定要去重新游览所有的旅游景点(当然也包括他自己的家)。为了制定计划,ZYB 根据他对景点的喜爱程度将所有景点排成了一个排列 P,在排列中越靠前表示 ZYB 越喜欢这个景点。
现在,ZYB 要开始制定他的游览计划。这个计划分为 K 天,每天 ZYB 将会选择一些景点进行游览,这个计划需要满足以下的条件:
- 为了保证不会无聊,ZYB 每天至少需要游览一个之前没有游览过的景点。
- 在第 K 天结束时,所有的景点都必须被恰好游览一次。
- 在任何一天的游览结束后,不能有这样一个景点,使得它没有被游览,但是存在一个受喜爱程度比它低的景点被游览了。
每一天,ZYB 会从家出发,走最短的路径把每个要游览的点都游览一遍(Notice:你每天选择的景点看作一个无序的集合,即 ZYB 可以任意确定游览的顺序,他总会选择可行方案中疲劳度最小的那一种),然后回到自己的家。定义每一天的疲劳度为他走过的边的数量。
作为一个健身狂魔,ZYB希望这 K 天的疲劳度之和最大,请你帮他制定计划,求出这个最大的疲劳度。
例如,在样例中,你可以为他选择 {2,4},{3,5,1},或是 {2,4,3},{5,1},这样他在第一天会经过 1−2−3−4−3−2−1 (ZYB可以路过一个景点但不游览),第二天经过 1−2−3−4−5−4−3−2−1,这样他的疲劳度是 6+8=14。如果选择 {2},{4,3,5,1},则疲劳度为 2+8=10。
输入格式
第一行两个整数 N,K,描述点数和天数。
第二行 N 个整数,描述排列 P。
接下来 N−1行,每行两个整数 x,y,描述这棵树。
输出格式
一行输出答案.
样例数据
样例输入
5 2
2 4 3 5 1
1 2
2 3
3 4
4 5
样例输出
14
子任务
Subtask1 (5 pts):K=2
Subtask2 (10 pts):N≤1000
Subtask3 (15 pts):N≤10000
Subtask4 (10 pts):1号点的度数不超过5,其他点的度数不超过 2。
Subtask5 (60 pts):无特殊限制。
对于所有数据均有 2≤K≤N≤NK≤200000。