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 $A_i$ 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 $A_i$. - 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 \le n \le 10^5$. - $1 \le k \le 100$. - $1 \le u, v \le n$. - $0 \le |A_i| \le 10^9$. ### Example Input: ``` 7 4 2 2 3 -4 -5 0 4 1 2 2 3 1 4 2 5 2 6 5 7 ``` Output: ``` 7 ```