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
问题 J: RXD, tree and sequence
时间限制: 6 Sec 内存限制: 128 MB提交: 1 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
输入描述
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.
输出描述
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-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
cnt: 43564
关于网站改版