Problem — 1919D. My solution runs in 93 ms, and I don't understand why.

Here is what I came up with: let's try to find the split boundary for the root between the subtree of the $$$0$$$-weight edge and the $$$1$$$-weight edge. We can notice that if the $$$0$$$-edge goes left, the boundary is max(pos(0), pos(second_to_last_1)), because there is exactly $$$1$$$ one in the right subtree. And if the $$$0$$$-edge goes right, the boundary is min(pos(0), pos(second_1)).

The only problem is that we can't exactly determine which way the $$$0$$$-edge goes, so we will try both options. Obviously, this just turns into a recursion (I should add that we search for the boundaries in O(log n)).

What bothers me is that it seems there could be a lot of branching in the recursion, resulting in an exponential or quadratic time complexity. And I can't figure out: are the test cases just weak, or is there some smart observation here to prove that it runs fast?

388357320

Can someone prove why this works fast, or find a countertest?