Мое решение ловит все время МЛ на 59 тесте.
Для каждой вершины находим все глубины его детей и храним это значение в мапе. После, когда даются запросы, находим k-того предка с помощью бинапов и суммируем кол-во всех детей, глубины которых >= k.
МЛ происходит из-за хранения всего этого в мапах. Но как можно решить эту задачу, не сохраняю на прямую кол-во глубин детей?
У тебя же при бамбуке будет n^2 работать решение
Этц задачу обычно дают когда объясняют трюк small to large
Ещё можно решить с помощью эйлерова обхода.
Кстати, да. Странно что оно у меня так далеко зашло. Возможно, как раз таки при бамбуке у меня МЛится, так еще и МЛ настает быстрее, чем ТЛ)
Те самые магический n log n, которые похожи на n² ?)
По моему, у других людей я видел как раз таки решение с эйлер. обход + бинапы. Но я до сих пор не понимаю, как их двоих скрестить
Их и не надо скрещивать.
Эйлеров обход даёт тебе массив такой что на отрезке [tin[v], tout[v]] находятся все вершины из поддерева v, дальше думай
Что такое бамбук?
Дерево в котором максимальная степень вершины \leq 2.
Спасибо за помощь, АС🥳
Олпрогеры выдумали термин для теории графов
Еще чуть-чуть и они придумают деревья с циклами
Кактусы?
(Шутка)
