TL;DR: можно ли одновременно поддерживать эйлеровым обходом LCA, сумму в поддереве и переподвешивание?

Дерево эйлерова обхода -- это способ представлять подвешенное неориентированное дерево массивом чисел. Построить это представление можно несколькими способами. У каждого есть свои плюсы и минусы. Здесь я хочу обсудить, можно ли придумать алгоритм, объединяющий плюсы всех описанных. Может быть, новичкам пост будет полезен как туториал. Первый способ -- выписать все рёбра дерева (ориентированные) в порядке обхода DFS'а. Так эйлеров обход определяется в Википедии.

     1
    / \
   2   5
  / \
 3   4

[1-2] [2-3] [3-2] [2-4] [4-2] [2-1] [1-5] [5-1]

Второй способ -- хранить вершины. Каждая вершина добавляется в массив дважды: когда мы в неё спускаемся и когда выходим. Каждому листу (кроме, возможно, корня) соответствует два последовательных вхождения.

     1
    / \
   2   5
  / \
 3   4

1 2 3 3 4 4 2 5 5 1

Третий способ -- также храним вершины, но каждая вершина добавляется в массив всякий раз, когда мы её посещаем (когда спускаемся из предка и поднимаемся из потомка).

     1
    / \
   2   5
  / \
 3   4

1 2 3 2 4 2 1 5 1

Далее, если явно не сказано иное, обход будет храниться в декартовом дереве по неявному ключу. first(v) и last(v) -- первое и последнее вхождение вершины в массив.

Итак, как же этим пользоваться?

Во-первых, заметим, что поддереву всегда соответствует отрезок. Значит, можно сводить запросы на поддеревьям к запросам на отрезках. Например, если мы хотим прибавлять к вершине и считать сумму в поддереве, можно построить дерево Фенвика на обходе 2-го типа. add(v, x) становится add(first(v), x) в Фенвике, а get_sum(v) становится get_sum(first(v), last(v)). С помощью небольшого трюка можно считать сумму на пути до корня: add(v, x) превращается add(first(v), x), add(last(v),  - x) в Фенвике, а get_sum_on_path_from_root(v) -- в get_sum(0, first(v)) (можете сами проверить на бумажке).

Эйлеровым обходом можно искать LCA. Используем третий тип. Будем хранить массив высот h, где h[i] = height(v[i]). Тогда lca(u, v) = v[argmin(first(u), first(v)) в h]. Почему? Потому что LCA(u, v) -- это самая высокая вершина между u и v в порядке обхода поиска в глубину. Я часто пишу этот метод вместо двоичного подъема -- быстрее и требует линию памяти.

Из того, что поддереву соответствует отрезок, можно извлечь ещё плюшек. В первом и третьем подходе можно переподвешивать дерево, просто перекинув кусок массива из начала в конец. Чтобы избежать некоторого геморроя, в третьем подходе можно не хранить последнюю вершину для корня (тогда у каждой вершины будет столько вхождений, чему равна её степень). Ещё можно удалять и добавлять рёбра (link-cut), вырезая отрезок из массива и вставляя его обратно. В третьем подходе надо аккуратно обрабатывать дублирующееся вхождение бывшего предка поддерева, которое появляется после его вырезания.

В общем, штука мощная и достаточно универсальная, но у меня есть несколько вопросов. Можно ли одновременно делать переподвешивание и LCA? сумму в поддереве и LCA? и так далее.

Вот небольшая табличка.

Заключительный вопрос (и главная цель этого поста): можете добавить плюсиков в таблицу и рассказать ещё что-нибудь, что можно делать эйлеровым обходом?

P.S. Не надо писать про хеви-лайт и линк-кат. Я знаю, что это и какие задачи ими можно решать, но хочется научиться выжимать максимум из эйлерова обхода.