RXD, tree and sequence

Problem Description

RXD has a rooted tree $T$ with size $n$, the root ID is $1$, with the depth of $1$ RXD has a permutation $P$ with size $n$. RXD wants to divide the permutaion into $k$ continuous parts For each part, he would calculate the depth of the least common ancestor of the part. And finally accumulate them. He wants to make the final result minimized. Please calculate the minimal answer. $1\leq k\leq n\leq 3\times 10^5, n\times k\leq 3\times 10^5$

Input

There are several test cases, please keep reading until EOF. For each test case, the first line consists of 2 integer $n, k$, which means the number of the tree nodes and the size of the permutaion, and $k$ means the number of parts. The next line consists of $n$ different integers, which means the permutation $P$. The next $n - 1$ lines consists of 2 integers, $a, b$, means a tree edge. It is guaranteed that the edges would form a tree. There are 6 test cases.

Output

For each test case, output an integer, which means the answer.

Sample Input

6 3

4 6 2 5 1 3

1 2

2 3

3 4

4 5

4 6

Sample Output

6

Source

2017 Multi-University Training Contest - Team 3

https://acm.hdu.edu.cn/showproblem.php?pid=6065