We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Tree Pruning

Tree Pruning

Problem
Submissions
Leaderboard
Discussions
Editorial

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:

  1. Remove the subtree rooted at node . Losing this subtree's weight increases the tree's total weight by .
  2. 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.

tree-pruning

Author

tuananhnb93

Difficulty

Advanced

Max Score

100

Submitted By

1675

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits

Choose a translation


  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy