Быстрые деревья

Вообще, если нужен универсальный алгоритм, не учитывающий какую-то специфику конкретных деревьев, то ИМХО лучшее предложил анонимус в самом начале в виде ссылок.

А причем тут пары узлов? Чем «найти наинизшую общую вершину для миллиарда пар узлов» отличается от «найти наинизшую общую вершину для двух миллиардов (или сколько их там будет) узлов»?

Для каждой пары — своя LCA со своим весом, который нужен в задаче принятия решения по группе из 2-100 пар.

для каждой пары своя общая вершина.

Именно.

связный список абсолютно никак не балансированный

Именно.

ИМХО лучшее предложил анонимус в самом начале в виде ссылок.

Возможно. При первом прочтении я пропустил важную деталь, что в список добавляются не все предки. Попробовать пока не было времени.

А можно предполагать, что почти всегда будет одна очень длинная ветка, а все остальные ветки будут небольшими «отростками» в некоторых местах этой длинной ветки? Можно ли предполагать что все деревья специфичны и для таких деревьев специальный алгоритм будет эффективнее универсального?

Меня смущает, что всего 100 тыс. узлов, и при этом самая длинная ветка 50 тыс. узлов.

В зависимости от вида деревьев задача либо очень простая, либо не очень простая. Какое дерево то хоть? Упорядоченное как-то или нет?

Тогда картинку нарисуй чтоль. Или как я выше сказал. Возми пустое дерево, добавь пару вычисли нужное, добавь ещё пару снова вычисли и так до победного пока тупо все данные не перегонишь. В итоге у тебя будет общая твоя точка которую в дальнейшем при добавлении ты просто будешь корректировать, а не вычислять всё заново каждый раз. Итоговая новая стурктура тупо заменит текущую и всё. Короче тупо перезапись, но уже с балансом вот и всюо.

А можно предполагать, что почти всегда будет одна очень длинная ветка, а все остальные ветки будут небольшими «отростками» в некоторых местах этой длинной ветки?

Нет. В других заданиях есть и более симметричные.

Если память позволяет, то попробуй дерево ван Эмде Боаса, главная особенность этой структуры — выполнение всех операций за время O(log(log(U))) независимо от количества хранящихся в ней элементов.

https://habr.com/ru/post/125499/

А в каком виде вообще дерево хранится? Это ведь не в оперативку тебе такое влезло? Это бд? Какая структура записей?

В любом желаемом. Выше ссылка на текстовый файл с пояснениями. Линейный массив родителей, линейный массив весов, короткие линейные массивы того, что следует искать.