QOJ.ac

QOJ

Time Limit: 7 s Memory Limit: 512 MB Total points: 100 Hackable ✓
统计

ZYB 所在的城市可以被抽象为一棵$N$个点的树,每个点都是一个旅游景点,其中一号点是 ZYB 的家(当然 ZYB 的家也是个旅游景点了)。

某一天,ZYB 突然决定要去重新游览所有的旅游景点(当然也包括他自己的家)。为了制定计划,ZYB 根据他对景点的喜爱程度将所有景点排成了一个排列 $P$,在排列中越靠前表示 ZYB 越喜欢这个景点。

现在,ZYB 要开始制定他的游览计划。这个计划分为 $K$ 天,每天 ZYB 将会选择一些景点进行游览,这个计划需要满足以下的条件:

  1. 为了保证不会无聊,ZYB 每天至少需要游览一个之前没有游览过的景点。
  2. 在第 $K$ 天结束时,所有的景点都必须被恰好游览一次。
  3. 在任何一天的游览结束后,不能有这样一个景点,使得它没有被游览,但是存在一个受喜爱程度比它低的景点被游览了。

每一天,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 \leq 1000$

Subtask3 (15 pts):$N \leq 10000$

Subtask4 (10 pts):$1$号点的度数不超过$5$,其他点的度数不超过 $2$。

Subtask5 (60 pts):无特殊限制。

对于所有数据均有 $2 \leq K \leq N \leq NK \leq 200\,000$。