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). 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.