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.

Hi, I'm a FiveAtomTree (5-indexed...), and I'm wondering how I can 0-index a BIT easily. I know I can just update upd(index+1, value), but at times it's really inconvenient.

I remember there was a comment on a contest announcement about it, but I forgot it and can't find it...

Anyone wanna hit me up?

Thanks~!

orz

Hello friends! I have tried to solve the 343D problem using a Segment Tree. When I submitted with the upper limit on the arrays of 4*MAX, it ended up with WA Test 10. Somehow, I was able to "fix" the code by changing the upper limit on the array to be 8*MAX instead of 4*MAX. Can anyone explain why this would result in a different answer (and why there is no index out of range (or some RE) when using 4*MAX)? Thanks for your help!

Submission for 4*MAX (WA): http://codeforces.me/contest/343/submission/19451573

Submission for 8*MAX (AC): http://codeforces.me/contest/343/submission/19451700