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

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

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$

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$

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.

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.

提交代码