6607: Rock Tree
内存限制:128 MB
时间限制:15.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
Professor Rockdu is interested in tree problems, and recently he has created a new data structure called Rock Tree.
Given a constant number k and a tree T={V,E} with V as the node set and E as the edge set, a non-empty set of nodes A is called a Rock Tree of T if and only if
Given a constant number k and a tree T={V,E} with V as the node set and E as the edge set, a non-empty set of nodes A is called a Rock Tree of T if and only if
- A⊆V
- All nodes of A are connected in T, which means for every pair of nodes u and v which are both in A, the nodes in the shortest path between u and v in T are all in A.
- The largest distance over every two nodes in A is not greater than k. The distance between two nodes u and v is defined as the number of nodes (including u and v) in the shortest path between u and v in the tree.
输入
The first line contains a single integer T (1≤T≤100), denoting the number of test cases.
For each test case, the first line contains two integers n,k (1≤n≤105, 1≤k≤n), indicating the number of nodes and the distance limit.
The second line contains n integers a1,a2,…,an (|ai|≤104), indicating the value of nodes.
Each of the following n−1 lines contains two integers u,v (1≤u,v≤n), denoting an edge between u and v. It is guaranteed that these edges form a tree.
It is guaranteed that the sum of n over all test cases won't exceed 106, and there are at most 4 test cases with n>50000.
For each test case, the first line contains two integers n,k (1≤n≤105, 1≤k≤n), indicating the number of nodes and the distance limit.
The second line contains n integers a1,a2,…,an (|ai|≤104), indicating the value of nodes.
Each of the following n−1 lines contains two integers u,v (1≤u,v≤n), denoting an edge between u and v. It is guaranteed that these edges form a tree.
It is guaranteed that the sum of n over all test cases won't exceed 106, and there are at most 4 test cases with n>50000.
输出
For each test case, output an integer denoting the maximum sum of node values in a single line.
样例输入 复制
2
7 3
3 2 -2 -6 6 3 -7
1 2
2 3
2 4
2 5
5 6
2 7
12 5
0 7 -1 3 -3 10 -1 -1 -5 -1 -4 -9
1 2
1 3
1 4
2 5
4 6
6 7
1 8
8 9
5 10
9 11
9 12
样例输出 复制
11
20