Доброго времени суток! Обращаюсь в просьбой помочь в решение одной задачи.
Задача из школьных архивов neerc'a : Нам дано дерево с N вершинами и N — 1 ребром. N <= 100000.
В каждой вершине есть число и нужно уметь отвечать на запросы : 1) Находить максимум из чисел на пути из вершины U в вершину V. 2) Изменять число в какой-либо вершине. Поискав в интернете способы решения, написал heavy-ligth decompisition, которая дает TL на очень многих тестах.
Вот код : http://pastie.org/3437084
Просьба посмотреть код и указать на ошибки. Буду рад любой помощи. Спасибо.
Ты как-то странно с LCA работаешь. Нам же, по сути, LCA один раз на запрос нужно узнать. Затем у нас запрос на два разбивается, и из них максимум просто выбираем.
Я потестил, если у меня в каждом запросе на каждом отрезке пути LCA запрашивать -- в два раза медленнее становится решение.
Та же самая задача на Тиумсе: http://acm.timus.ru/problem.aspx?space=1&num=1553 Мой код: http://pastie.org/3437258 (LCA я деревом отрезков ищу там)
Да, спасибо. Вроде понятно