You will be given a connected undirected tree. Each node will have an associated integer that we will call its value. We also define the value of a subset of nodes as the sum of values of the nodes in the subset. Consider the subsets of nodes of this tree whose size is between 1 and K, inclusive, and satisfy the property that within each subset no node is an ancestor (Formally, we say that node u is an ancestor of node v if u lies on the path from v to the root of the tree) of another. We will call these subsets the K-anti-ancestral subsets of the tree. Your task is, given the tree, to find the K-anti-ancestral subset of maximum value. As an example, consider the tree below. Each node is named with a capital letter and the value of each node is the integer below the letter: Suppose K = 3. Then the subset of nodes {A}, {B, E}, {C, E}, {D, G} and {B, E, F} are some of the K-anti-ancestral subsets of the tree, because they all have between 1 and K = 3 nodes and within each subset there doesn’t exist a pair of nodes such that one is an ancestor of the other. On the other hand, {A, B} is not a K-anti-ancestral subset because A is an ancestor of B, {A, G} isn’t one because A is an ancestor of G and {C, B, D} isn’t one either because B is an ancestor of both C and D. The subset {C, D, E, F}, even though it doesn’t contain a node that is an ancestor of another one, is not a K-anti-ancestral subset because it has 4 > K = 3 nodes. Similarly, the empty set ∅ is not one either because it contains 0 elements. The value of the K-anti-ancestral subset {A} is 6; the value of {B, E} is 3 + 1 = 4; the value of {C, E} is 4 + 1 = 5; the value of {D, G} is -1 + 1 = 0 and the value of {B, E, F} is 3 + 1 + (-5) = -2. Since the tree is small, it’s easy to convince yourself by inspection that the maximum possible value of any K-anti-ancestral subset is 6. However, notice that there might be several ways to achieve the maximum value: {A} and {C, E, G} both have value 6. You are only asked to find the value of the maximum K-anti-ancestral subset so it doesn’t really matter how many of them exist. Input The input file contains several test cases (at most 50). Each test case is described on three lines:
2/3 • The first line contains two integers N and K, the number of nodes in the tree and the parameter K as explained above. Assume 2 ≤ N ≤ 105 and 1 ≤ K ≤ 100 (notice that these constraints guarantee that there will always exist at least one K-anti-ancestral subset, e.g. by taking a single node). The nodes will be numbered 0 through N − 1. The root of the tree will always be node 0. You can assume that the tree will always be connected, i.e., there will always exist a path connecting any pair of nodes. • The second line contains N integers separated by spaces. These integers represent the values of nodes 0 through N − 1 (the first integer is the value of node 0, the second integer is the value of node 1 and so on — the last integer is the value of node N − 1). The value of any node will always be between -100 and 100, inclusive. • The third line contains the description of the tree. It contains N − 1 integers separated by spaces that represent the parent nodes of nodes 1 through N − 1 (the first integer is the parent of node 1, the second integer is the parent of node 2 and so on — the last integer is the parent of node N − 1). Notice that since 0 is always the root of the tree it doesn’t have a parent and that’s why this line contains only N − 1 numbers instead of N . The last line contains two zeros and should not be processed. See the sample input for clarification about this format. The first test case is the tree given in the figure above. Output For each test case, output one integer on a single line — the maximum possible value of any K-anti- ancestral subset. Sample Input 7 73 6 3 4 -1 1 -5 1 011005 21 -1 1 0 33 123 00 88 12345678 0123456 44 -27 -45 -67 -98 202 00 Sample Output 6 1 5
3/3 8 -27