Задача — 1919D. Мое решение работает за 93 мс, и я не понимаю почему.
Что я придумал: попытаемся найти для корня границу разделения между поддеревом ребра веса $$$0$$$ и веса $$$1$$$. Можно заметить, что если $$$0$$$-ребро ведет влево, то граница — это max(pos(0), pos(предпоследней_1)), потому что в правом поддереве ровно $$$1$$$ единица. А если $$$0$$$-ребро ведет вправо, то граница — это min(pos(0), pos(второй_1)).
Проблема лишь в том, что мы не можем точно определить, куда именно ведет $$$0$$$-ребро, так что будем пробовать оба варианта. Понятно, что это просто рекурсия (надо добавить, что границы за O(logn) ищем).
Меня смущает то, что, кажется, ветвлений у рекурсии может быть много и получится экспонента или квадрат. И я не могу понять: это тест-кейсы плохие, или тут можно заметить что-то умное и доказать, что работает за быстро.
Может кто-то доказать, почему это работает быстро, или найти контртест?
