
106  ZOJ Monthly, May 2011  G
Given a graph with N vertices (labeled 1 to N). The graph is connected, undirected and acyclic, and also known as an "unrooted tree". Each vertex has a weight, which is an integer. The total weight of a tree, is the summation of the weight of all its vertices. Follow the instruction below to "cut the tree" exactly K times: (1) Choose an edge of the tree, and remove it. Now you are asked to calculate, after all those done, the minimal and maximal weight of the tree we finally get. Input Mutiple test cases, process to the end of file. Each test case consists of three parts. First part, a single line with two integers N (1<=N<=1000) and K (0<=K<=20, K<N). Second part, a single line with N integers, the weight of vertices labeled 1 to N. The weight is in range [1000,1000]. Third part, N1 lines, each line with two integers X and Y represents an edge between vertex X and vertex Y. Output For each test case, output one line with two integers, the minimal and maximal weight of the tree we finally get. Sample Input 2 1 1 1 1 2 6 0 3 1 2 3 4 0 1 2 1 3 2 4 3 5 3 6 6 1 3 1 2 3 4 0 1 2 1 3 2 4 3 5 3 6 Sample Output 1 1 3 3 1 4 Author: CUI, Tianyi 