Responsive image

问题 1818 --RXD, tree and sequence

1818: RXD, tree and sequence

时间限制: 6 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

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≤k≤n≤3×105,n×k≤3×105

输入描述

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, output an integer, which means the answer.

样例输入

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

样例输出

6

来源

 

[提交][状态]
ACM算法攻关部