UPD2: Ниженаписанное не имеет отношения к тому, что спрашивал топикстартер. Зато объясняет эту задачу: 191C - Дураки и дороги

Не знаю насчёт кластеризации, могу рассказать другое решение за n log^2 n.

Разобьём каждый путь на две части части вершиной, являющейся LCA концов. Теперь пути идут только снизу вверх. Запишем в каждую вершину список путей, которые в ней начинаются и идут вверх. Теперь пройдёмся DFS'ом, помня для каждой вершины multiset глубин верхних концов путей, которые начались где-то ниже и ещё не закончились к текущему моменту. Тогда ответ для ребра, торчащего из текущей вершины есть мощность этого мультисета. Как его пересчитывать? Очевидно, что он есть просто объединение таких мультисетов для всех детей, из которого мы выкинули все пути заканчивающиеся ровно в нас. Как брать быстро объединение? Известный факт, что если примёрдживать меньший сет к большему за размер меньшего сета, то амортизированно выйдет n log n операций добавления в сет, что даст асимптотику n log^2 n. Очень популярная в прошлом-текущем сезоне идея, кстати.

UPD: интересно, что факт об амортизированной количестве добавлений log n на вершину доказывается как раз из соображений, похожих на использующиеся в heavy-light декомпозиции. По сути, такое решение соотносится с heavy-light-решением приблизительно как соотносятся для задачи на массиве подсчёт в оффлайне ответа на все запросы сразу с онлайн-решением деревом отрезков.

К слову, это решение сильно сложнее чем надо: так как сумма это обратимая операция, можно было просто дописать в нижний конец пути +1, в верхний — -1, и просто накапливать ответ. Но с каким-нибудь максимумом так не прошло бы.

Ну навскидку довольно просто можно за O(Q * (logN + K) + (Q / K) * (K + N * logN)), правда тоже без кластеризации. Если правильно выбрать K, то для макстеста будет порядка 128 миллионов операций. Идея следующая: будем для каждой вершины хранить максимум на 1, 2, 4, 8, ... предков выше. Если бы не было изменений, то ясно как отвечать на запрос за O(logN). Теперь применим принцип отложенной реализации, а именно: будем складывать запросы изменения в массив и затем применять их всех сразу, когда массив достигнет размера K. Получается, чтобы ответить на запрос, нам надо помимо поиска максимума в дереве за O(logN), еще пройти по всем запросам изменения, которые все еще не были применены и для тех, которые лежат на нашем пути, сравнить максимум с уже найденным. Получается, что отвечаем на один такой запрос мы за O(K + logN). Ну а перестраиваем все дерево с информацией о предках мы одним дфсом за O(K + NlogN), что происходит Q / K раз.

Я её решал таким образом в далёком 2007 году. Это как Heavy-Light декомпозиция, только я тогда не знал такой декомпозиции. Мы просто ограничиваем длину цепей до sqrt(N). Нам не нужно в таком случае юзать деревья отрезков для RMQ т.к. длина цепей ограничена корнем из N, мы можем запрос на изменение уровня радиации в цепи обрабатывать за O(длина цепи) пересчитывая каждый раз массив дающий значение максимума на префиксе. Количество цепей всего, может быть порядка O(N) (так же как для HL) но на пути между двумя вершинами будет не более двух корней. Для LCA юзаются цепи — у каждой вершины известны предок, и то к какой цепи она принадлежит, а каждая цепь знает самую высокую свою вершину "стартовую".

Раз уж пошел небольшой оффтоп, поделюсь своим решением.

Сначала запустим dfs и для каждой вершины x запомним время входа в нее (s[x]) и время выхода (e[x]). Далее заметим, что если вершина y лежит в поддереве вершины x, то вершина z лежит на пути из x в y тогда и только тогда, когда s[x] <= s[z] <= s[y] и e[x] >= e[z] >= e[y]. Тогда максимум радиации на пути из x в y можно найти одним запросом к квадродереву, в котором каждой вершине x соответствует точка (s[x], e[x]). Ну и для нахождения ответа для двух произвольных вершин находим LCA и производим два запроса к дереву.

http://pastebin.com/C9yxuGnb

Осторожно: исходник был написан давно и по-наркомански, например, хранит граф

Идея: представим дерево как дерево примерно sqrt(N) групп примерно sqrt(N) элементов каждая. Храним для каждой вершины ответ запроса до корня группы (считается, что корень группы либо корень дерева, либо сам принадлежит группе выше). Изменение — изменение в одной группе, она просто пересчитывается. Запрос (u,v) — поднимаемся от u, пока не дошли до предка v, и симметрично.

Примечание: нужно это делать очень аккуратно. Размер каждой группы может быть N, поэтому запрос на обновление вызывается только для потенциально изменившейся ее части. Гарантируется, что поддерево любого потомка корня группы внутри этой группы не превосходит sqrt(N)

Upd. madskillz-картинка.