- Prepare
- Algorithms
- Dynamic Programming
- Tree Pruning

# Tree Pruning

# Tree Pruning

A tree, , has vertices numbered from to and is rooted at vertex . Each vertex has an integer weight, , associated with it, and 's *total weight* is the sum of the weights of its nodes. A single *remove operation* removes the subtree rooted at some arbitrary vertex from tree .

Given , perform up to remove operations so that the total weight of the remaining vertices in is maximal. Then print 's maximal total weight on a new line.

**Note:** If 's total weight is already maximal, you may opt to remove nodes.

**Input Format**

The first line contains two space-separated integers, and , respectively.

The second line contains space-separated integers describing the respective weights for each node in the tree, where the integer is the weight of the vertex.

Each of the subsequent lines contains a pair of space-separated integers, and , describing an edge connecting vertex to vertex .

**Constraints**

**Output Format**

Print a single integer denoting the largest total weight of 's remaining vertices.

**Sample Input**

```
5 2
1 1 -1 -1 -1
1 2
2 3
4 1
4 5
```

**Sample Output**

```
2
```

**Explanation**

We perform remove operations:

- Remove the subtree rooted at node . Losing this subtree's weight increases the tree's total weight by .
- Remove the subtree rooted at node . Losing this subtree's weight increases the tree's total weight by .

The sum of our remaining positively-weighted nodes is , so we print on a new line.