QOJ.ac

QOJ

Time Limit: 7 s Memory Limit: 512 MB Total points: 100 Hackable ✓
[+2]
统计

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},这样他在第一天会经过 1234321 (ZYB可以路过一个景点但不游览),第二天经过 123454321,这样他的疲劳度是 6+8=14。如果选择 {2},{4,3,5,1},则疲劳度为 2+8=10

输入格式

第一行两个整数 N,K,描述点数和天数。

第二行 N 个整数,描述排列 P

接下来 N1行,每行两个整数 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):N1000

Subtask3 (15 pts):N10000

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

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

对于所有数据均有 2KNNK200000