Задача
Дано дерево на $$$n$$$ вершинах, в вершине $$$v$$$ записано число $$$a_v$$$. Поступают запросы двух видов:
- Найти максимальное число на кратчайшем пути из вершины $$$u$$$ в вершину $$$v$$$.
- Сделать $$$a_v = x$$$.
Варианты решений
Эта задача очень известна, поэтому скорее всего вам в голову пришло решение, использующее Heavy-Light Decompositon (или Link-Cut Tree, если вы большой любитель splay-деревьев). Первый вариант в стандартной реализации работает за $$$O(log^2~ n)$$$, второй работает за $$$O(log~ n)$$$, однако для его использования нужны более специфичные знания. Хочется добиться более хорошей асимптотики HLD, используя какие-то несложные идеи. Оказывается, что это возможно.
$$$O(log^2~ n)$$$ на запрос
Постараемся разбить дерево на вершинно непересекающиеся пути так, чтобы при запросе нам потребовалось разбить путь между вершинами из запроса на небольшое количество отрезков так, чтобы каждый из них лежал в каком-то одном пути.
Назовем ребро тяжелым, если оно соединяет вершину с ее ребенком-поддеревом с самым большим размером (если таких несколько, то выберем любого), остальные ребра будем считать легкими. Если какие-то два тяжелых ребра имеют общую вершину, то объединим их в один путь. В конце концов мы разобьем дерево на пути, состоящие из тяжелых ребер (нетрудно понять, что такие пути не могут никак пересекаться в силу определения тяжелого ребра).
Давайте покажем, что на любой вертикальный путь можно разбить на $$$O(log~ n)$$$ частей, каждая из которых полностью лежит в одном пути. Будем подниматься из нижней вершины вверх. Если мы сменили текущий путь, это означает, что мы перешли по легкому ребру, а значит размер поддерева, в котором мы сейчас находимся, увеличился в хотя бы $$$2$$$ раза. Так как вершин в дереве $$$n$$$, мы не сможем сменить путь более чем $$$log~ n$$$ раз. А значит мы добились того, чего хотели.
Теперь, что бы ответить на запрос, достаточно узнать максимум на путях $$$(lca(u, v), u)$$$ и $$$(lca(u, v), v)$$$. Это можно сделать, например, используя дерево отрезков (отсюда $$$O(log^2~n)$$$).
Для смены $$$a_v$$$ достаточно сделать один запрос в дерево отрезков.
В данном посте не будем рассматривать стандартную реализацию HLD, так как есть люди, которые сделают это лучше меня.
$$$O(log~ n)$$$ на запрос
Для доказательства асимптотики в предыдущем пункте мы использовали тот факт, что переходя с одного пути на другой, поддерево увеличивается хотя бы в $$$2$$$ раза. Развивая эту идею, можно добиться лучшей асимптотики.
А что, если попытаться сделать такую структуру, что взятие максимума на каком-то отрезке пути на каждой своей операции увеличивает какую-то величину $$$ \le n$$$ хотя бы в $$$2$$$ раза? Тогда мы как раз добьемся того, чего хотели.
Основная проблема кроется в дереве отрезков. Оно отвечает на запрос за $$$O(log~ n)$$$ (или $$$O(log(r - l))$$$, если использовать реализацию снизу). Это происходит из-за того, что мы делим текущий отрезок пополам никак не пользуясь размерами поддеревьев. Давайте это исправим. Для этого нам потребуется использовать вместо дерева отрезков другое бинарное дерево.
Рассмотрим какой-то путь декомпозиции $$$v_1, v_2, \dots, v_k$$$. Давайте мысленно уберем ребра между соседними вершинами, а за $$$w_i$$$ обозначим размер поддерева $$$v_i$$$, которое осталось у вершины. Пусть $$$W = \sum_{i=1}^{k} w_i$$$. Найдем первый такой индекс $$$j$$$, что $$$\sum_{i=1}^{j} w_i \ge \frac{W}{2}$$$. Сделаем вершину $$$v_j$$$ корнем нашего бинарного дерева, а для определения левого и правого ребенка рекурсивно запустимся от левой и правой половины пути. Теперь мы умеем строить какое-то странное дерево, но непонятно чем оно лучше обычного дерева отрезков.
Для начала подумаем, как в таком дереве отвечать на запрос максимума на отрезке. Для этого посмотрим на вершины пути, которые являются самой левой и самой правой вершиной отрезка ($$$l$$$ и $$$r$$$), на котором нам нужно посчитать максимум. Найдем их позицию в построенном нами дереве. Теперь, чтобы ответить на запрос, нам надо подняться от $$$l$$$ до $$$lca(l, r)$$$ в нашем дереве, обновляя ответ через значение текущей вершины, а также значение ее правого поддерева, если сама вершина является левым сыном (для меня, такой способ ответа на запрос сильно напомнил дерево отрезков снизу). Аналогично нужно подняться от $$$r$$$.
Осталось посчитать асимптотику. Если мы посмотрим на $$$\sum w_i$$$ в текущем поддереве нашей структуры, то в силу построения дерева при переходе в предка она увеличивается в хотя бы $$$2$$$ раза. Тогда если следить за такой величиной, можно понять, что мы добились $$$O(log~ n)$$$ на запрос, так как если мы поднимаемся при ответе на запрос в текущем пути данное значение увеличивается хотя бы $$$2$$$ раза, а также, если мы переходим по легкому ребру, $$$\sum w_i$$$ снова увеличивается в два раза (теперь уже в силу изначального разбиения на пути). Получается, мы добились того, чего хотели (довольно очевидно, что данная величина не может превышать $$$n$$$).
Для обновления $$$a_v$$$ достаточно взять нужную вершину в построенном на пути бинарном дереве и обновить всех ее предков (доказательство времени работы аналогично).
Для большего понимания, предлагаю ознакомиться с кодом:
Понятно, что это не тот код, который хочется писать на олимпиаде, однако мне кажется, что узнавать новое всегда интересно.
PS
Не судите строго, это мой первый пост на подобные темы. Если где-то заметите опечатку, прошу сообщить.
Хотелось бы сказать спасибо моим друзьям, которые помогли найти хоть какую-то информацию о данной модификации.
Кажется, что на данную структуру можно обобщить массовые операции, т.к она очень похожа на дерево отрезков снизу (но сейчас 2 часа ночи и как-то не хочется об этом думать).
