ЗадачаProblem — [1919D](https://codeforces.me/contest/1919/problem/D). ↵
Мое решение работает за 93 мс, и я не понимаю почему.↵
↵
Что я придумал: попытаемся найти для корня границу разделения между поддеревом ребра веса $0$ и веса $1$. Можно заметить, что если $0$-ребро ведет влево, то граница — это `max(pos(0), pos(предпоследней_1))`, потому что в правом поддереве ровно $1$ единица. А если $0$-ребро ведет вправо, то граница — это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))`. ↵
↵
Проблема лишь в том, что мы не можем точно определить, куда именно ведет $0$-ребро, так что будем пробовать оба варианта. Понятно, что это просто рекурсия (надо добавить, что границы за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](https://codeforces.me/contest/1919/submission/388361656)↵
↵
Может кто-то доказать, почему это работает быстро, или найти контртестCan someone prove why this works fast, or find a countertest?
