Remove subtree - MarisaOJ: Marisa Online Judge

Remove subtree

Time limit: 1000 ms
Memory limit: 256 MB
You are given a tree of n vertices rooted at 1, vertex i has the number Ai on it. Find the maximum possible sum of all vertices can be obtained by removing at most k subtrees. ### Input - The first line contain 2 integers n,k. - The second line contains n integers Ai. - The next n−1 lines, each line contains 2 integers u and v, there is an edge between u and v. ### Output - Print the maximum sum. ### Constraints - 1≤n≤105. - 1≤k≤100. - 1≤u,v≤n. - 0≤|Ai|≤109. ### Example Input: 74223-4-504122314252657 Output: 7