Hard Tree Problem
Difference between en1 and en2, changed 77 character(s)
This problem recently appeared in the GSA-ULTRA competition (which ended last Sunday). ↵

Can anyone propose a solution?↵

We have a N <= 100,000 node rooted tree.↵

All nodes have integer weights (**and each weight is between 0 and 1000**). ↵

Let the height of the tree be the longest path to a leaf from the root (and the root is just defined to be node 0). 
The "longest" path here refers to the path with largest sum of node weights. You can change the weight of W nodes (W <= 50,000) to 0. Find the minimum height you can get if you do this optimally.↵


History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English conqueror_of_conqueror 2020-08-13 07:03:41 77
en1 English conqueror_of_conqueror 2020-08-13 07:02:03 506 Initial revision (published)