题目描述

给定一棵有 $n$ 个顶点的树，以及顶点 $1,2,\ldots,n$ 的一个排列 $p_1,p_2,\ldots,p_n$。

在排列的相邻位置之间进行切分。位置 $i$ 与 $i+1$ 之间的切分记为 切分点 $i$（$1\le i<n$）。选择 $k-1$ 个不同的切分点后，排列被分成 恰好 $k$ 个非空连续块。

对于一个块，取出其中出现的所有顶点，并保留树中两个端点都在该块内的边，得到这个块诱导的子图。记该子图的连通分量数为这个块的得分。请计算所有合法切分方案中，各块得分之和的最大值。

输入格式

从文件 split.in 中读取数据。

第一行包含两个整数 $n,k$。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树中有一条连接顶点 $u$ 和 $v$ 的无向边。若 $n=1$，这部分没有输入行。

最后一行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示给出的排列。

输出格式

输出到文件 split.out 中。

输出一个整数，表示最大得分之和。

样例

4 2
1 2
2 3
3 4
1 2 3 4

2

4 2
1 2
1 3
1 4
2 3 4 1

4

5 5
1 2
2 3
3 4
4 5
3 1 5 2 4

5

1 1
1

1

样例解释

样例 #1 解释

无论选择切分点 $1$、$2$ 还是 $3$，两个块诱导的子图各有一个 连通分量，因此总得分都是 $2$。

样例 #2 解释

选择切分点 $3$ 时，左块的三个顶点彼此没有边，得到 $3$ 个连通分量， 右块只有顶点 $1$，得到 $1$ 个连通分量，总分为 $4$，这是最大值。

样例 #3 解释

每个块都只有一个顶点，所以每个块的得分为 $1$，总得分为 $5$。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 100000$；
• $1\le k\le \min(n,20)$；
• $1\le u,v\le n$ 且 $u\ne v$，给出的 $n-1$ 条边互不重复并构成一棵树；
• $p_1,p_2,\ldots,p_n$ 是 $1,2,\ldots,n$ 的一个排列。

本题采用子任务捆绑计分。每个子任务包含若干测试点，只有通过该子任务的全部测试点，才能获得该子任务的分数。各子任务分别计分。

子任务编号	分值	额外约束
$1$	$10$	$n\le 18$
$2$	$15$	$k\le 2$
$3$	$25$	$n\le 2000$
$4$	$50$	无特殊限制

大样例下载