# RXD, tree and sequence

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

## 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.
$1\leq k\leq n\leq 3\times 10^5, n\times k\leq 3\times 10^5$

## Input

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

liuyiding

## Source

2017 Multi-University Training Contest - Te