Двоичные подъёмы и LCA

Наименьший общий предок (LCA) вершин $u$ и $v$ — самая глубокая вершина, являющаяся предком обеих.

Наивно: подниматься от $u$ к корню и на каждом шаге проверять критерием через tin/tout, не стал ли текущий предок предком и для $v$. Ответ верный, но на бамбуке это $O(n)$ на запрос.

Идея

Выпишем предков $u$ снизу вверх. Сначала идут вершины, не являющиеся предками $v$, потом — являющиеся, и переключение происходит ровно один раз. То есть перед нами массив вида $0,0,\ldots,0,1,1,\ldots,1$, и нужна первая единица.

Такое ищется бинарным поиском — только массива у нас нет, по нему нельзя индексироваться. Зато можно заранее насчитать прыжки на степени двойки и набирать нужную высоту по битам, от старшего к младшему. Это экспоненциальный поиск в чистом виде.

Предподсчёт

up[k][v] — куда попадём, поднявшись из $v$ на $2^k$ рёбер. Считается по индукции: прыжок на $2^k$ — это два прыжка на $2^{k-1}$.

int LOG = 1;
while ((1 << LOG) <= n) LOG++;
vector<vector<int>> up(LOG, vector<int>(n));

for (int v = 0; v < n; v++) up[0][v] = (par[v] == -1 ? v : par[v]);
for (int k = 1; k < LOG; k++)
    for (int v = 0; v < n; v++)
        up[k][v] = up[k - 1][up[k - 1][v]];

Корень считаем своим родителем. Тогда слишком длинный прыжок упирается в корень и остаётся там — и не надо отдельно проверять выход за границу.

Время и память — $O(n \log n)$.

Способ первый: через tin/tout

Поднимаем $u$, пока не перескочили: прыжок делаем только если он не приводит в предка $v$.

int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    if (isAncestor(v, u)) return v;
    for (int k = LOG - 1; k >= 0; k--)
        if (!isAncestor(up[k][u], v)) u = up[k][u];
    return up[0][u];
}

Две проверки в начале обязательны: если $u$ уже предок $v$, ни одного прыжка не будет, и финальный up[0][u] уведёт на уровень выше ответа.

Способ второй: выровнять высоты

Первый способ несимметричен: одну вершину поднимаем, вторую держим. Второй способ симметричен и обходится без tin/tout — нужны только глубины.

Сначала поднимаем более глубокую вершину до уровня второй. Разность глубин раскладывается по битам:

int jump(int v, int k) {
    for (int i = 0; i < LOG; i++) if (k >> i & 1) v = up[i][v];
    return v;
}

Теперь вершины на одной высоте. Поднимаем обе синхронно: прыжок делаем, только если попадаем в разные вершины.

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    u = jump(u, dep[u] - dep[v]);
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--)
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}

Почему совпадение вершин означает «перелетели»: раз обе вершины на одной высоте, они одинаково удалены от своего LCA. Прыжок, перескакивающий LCA, приводит обе в одну и ту же вершину; прыжок короче — в разные.

Условие u == v после выравнивания обязательно: оно ловит случай, когда одна вершина оказалась предком другой.

Проверено: оба способа совпали с подъёмом по родителям на 20 000 деревьях, суммарно около 1,4 миллиона запросов.

Цена памяти

$O(n \log n)$ памяти — это не только формальность. При $n = 10^5$ массив занимает $10^5 \cdot 17 \cdot 4 \approx 6{,}8$ МБ. Кэш последнего уровня у типичного процессора — единицы мегабайт, так что таблица в него не помещается, и обращения идут в оперативную память.

Разница между попаданием в кэш и походом в память — порядок величины. Решение не перестанет работать, но константа вырастет заметно.

Если это мешает, есть прыжковые указатели с линейной памятью — тот же логарифм на запрос, но $O(n)$ памяти.