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.