Тренировочная сессия 21: двоичные подъёмы — LCA и максимум на пути СЕССИЯ

Что тренируем сегодня

Сегодняшняя тренировка — про заготовку, из которой вырастает целый класс решений: таблицу двоичных подъёмов, где для каждой вершины хранится её предок на $2^k$ уровней выше. Строится она за пятнадцать строк, а дальше отвечает на вопросы «кто общий предок», «какая вершина ровно на k шагов выше», «каково расстояние», «какое максимальное ребро на пути».

Первая задача — про наименьшего общего предка (сокращённо LCA, от least common ancestor) и середину пути. Спрашивают, сколько вершин дерева равноудалены от двух заданных. Прямой ответ — обойти дерево на каждый запрос, но запросов сто тысяч. Правильный — заметить, что всё определяется одной вершиной: серединой пути между заданными.

Вторая задача — особенная, и стоит сказать об этом прямо. Все остальные тренировки цикла построены вокруг одного приёма; здесь их честно два, потому что поодиночке они задачу не решают. Нужен минимальный остов, построенный Краскалом, — и нужен максимум ребра на пути внутри этого остова, который даёт таблица подъёмов. Убери любую половину, и решения не останется. Именно так выглядит законная связка двух приёмов, в отличие от двух тем, просто оказавшихся в одной статье.

Поэтому и структура теории сегодня другая: сначала главный приём, потом короткая справка по системе непересекающихся множеств — не как отдельная тема, а как инструмент, без которого вторая задача не заработает, — и только затем их совместное применение.

---

Теория

Двоичные подъёмы. Для каждой вершины заранее считается её предок на $2^k$ уровней выше — и из этой одной таблицы получаются ответы на целый класс вопросов о путях в дереве.

Для каждой вершины заранее считается таблица up[k][v] — вершина, стоящая ровно на $2^k$ уровней выше v. Имея её, можно подняться на любую высоту h, разложив h по двоичным разрядам: подъём на 13 — это подъёмы на 8, на 4 и на 1.

Когда применять:

• нужны ответы на много запросов о парах вершин дерева: расстояние, общий предок, середина пути;
• нужна вершина «ровно на k уровней выше данной»;
• нужен максимум, минимум или сумма по пути между вершинами (тогда рядом с up кладётся вторая таблица с этой же структурой).

Как решать:

1. Подвесить дерево за вершину 1, обходом посчитать глубины и up[0][v] — непосредственного предка. Для корня положить up[0][1] = 1 — «предок корня это он сам».
2. Заполнить таблицу: up[k][v] = up[k-1][ up[k-1][v] ]. Внешний цикл — по k, внутренний — по вершинам; иначе на момент вычисления нужные значения ещё не готовы.
3. Подъём на h: пройти по битам h, и для каждого установленного бита k сделать v = up[k][v].
4. Общий предок: сначала поднять более глубокую вершину до уровня второй. Если они совпали — это и есть ответ. Иначе прыгать обеими сразу от больших k к меньшим, но только когда предки различаются; в конце ответ — up[0][v].

Мини-пример на шаге 4. Пусть после выравнивания вершины u и v разные. Пробуем прыжок на 8: если up[3][u] == up[3][v], значит перепрыгнули общего предка — не прыгаем. Пробуем на 4, на 2, на 1 — каждый раз прыгаем, только если предки всё ещё разные. В итоге u и v останавливаются ровно на дочерних вершинах общего предка, и ответ — их предок.

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

Где ошибаются в узнавании: считают, что LCA нужен только там, где про него сказано прямо. На деле его признак другой — много запросов о парах вершин дерева. Расстояние, середина пути, «лежит ли вершина на пути», максимум на пути — всё это LCA, хотя слов «общий предок» в условии нет.

Сложность приёма: $O(n\log n)$ на предпосчёт и память, $O(\log n)$ на запрос.

Каркас приёма:

Подчинённая заготовка: система непересекающихся множеств и Краскал. Вторая сегодняшняя задача — единственное место в цикле, где одного приёма не хватает: чтобы получить путь, на котором мы ищем максимум подъёмами, этот путь надо сначала построить, а строится он алгоритмом Краскала. Поэтому здесь короткая справка — не как отдельная тема, а как инструмент, без которого главный приём не заработает.

Система непересекающихся множеств хранит разбиение объектов на группы и умеет ровно две вещи: сказать, в одной ли группе два объекта, и слить их группы. Устроена она как лес: у каждого объекта есть «представитель», и поиск идёт по ссылкам вверх до корня, попутно перевешивая пройденные вершины сразу на корень — это и называется сжатием путей. Вместе с объединением по размеру обе операции работают практически за константу.

Краскал поверх неё выглядит так: отсортировать рёбра по весу и идти по ним от лёгких к тяжёлым, добавляя ребро в остов тогда и только тогда, когда его концы ещё в разных группах. Почему это даёт минимальный остов: если бы в оптимальном остове не было очередного лёгкого ребра, его можно было бы добавить, получить цикл и выкинуть из цикла ребро потяжелее — вес не вырос бы. Знакомый обменный аргумент с «Плато», только про рёбра.

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

Применение: остов, обязанный содержать заданное ребро.

Есть связный взвешенный граф и его минимальное остовное дерево весом $W$. Для ребра $e$ спрашивают: каков минимальный вес остова, в котором $e$ обязательно присутствует? Ответ считается по формуле, без единого перестроения.

Когда применять:

• «минимальный остов, содержащий ребро $i$» — для каждого ребра;
• «на сколько подорожает связь, если это ребро обязательно / если это ребро сломалось»;
• «второе по минимальности остовное дерево» — та же техника с небольшой поправкой.

Как решать:

1. Построить минимальный остов Краскалом, запомнив его вес $W$ и пометив, какие рёбра в него вошли.
2. На рёбрах остова построить таблицу двоичных подъёмов, добавив рядом с up таблицу mx — максимум веса ребра на подъёме.
3. Если ребро $e$ уже в остове — ответ $W$.
4. Иначе ответ $W + w(e) - M$, где $M$ — максимальный вес ребра на пути между концами $e$ внутри остова.

Почему так. Добавим $e$ к остову — появится ровно один цикл, состоящий из $e$ и пути между его концами. Чтобы снова получить дерево, надо выкинуть одно ребро этого цикла; выкидывать сам $e$ нельзя (он обязан остаться), значит выгоднее всего убрать самое тяжёлое ребро пути. Это даёт остов с $e$ весом $W + w(e) - M$.

Дешевле не бывает, и это видно через Краскала. Представьте, что мы запускаем Краскал заново, но заранее объявляем концы $e$ соединёнными (само ребро $e$ бесплатно уже взято). Алгоритм пойдёт по тем же рёбрам в том же порядке и примет те же решения — кроме одного момента. Рёбра пути между концами $e$ добавлялись бы как обычно, но самое тяжёлое из них к своей очереди окажется лишним: его концы уже связаны остальными рёбрами пути плюс бесплатным $e$. Значит от старого остова отвалится ровно одно ребро — то самое $M$.

Мини-пример. Остов: 1 — 3 весом 1, 3 — 2 весом 2, вес остова 3. Ребро 1 — 2 весом 5 в остов не вошло. Путь между 1 и 2 в остове — рёбра весов 1 и 2, максимум 2. Ответ для ребра 1 — 2: $3 + 5 - 2 = 6$.

Где ошибаются в узнавании: видят «для каждого ребра» и добросовестно перестраивают остов $m$ раз. Признак того, что нужен пересчёт, а не перестроение, всегда один: величина спрашивается для каждого элемента входа, а сам по себе один ответ считается быстро.

Сложность приёма: $O(m\log m)$ на Краскала, $O(n\log n)$ на таблицы, $O(\log n)$ на ребро.

Каркас приёма — максимум веса ребра на пути (mx строится вместе с up):

---

Задача 1 — CF ~2100 — «A and B and Lecture Rooms»

Что дано

Дано дерево из n вершин. Затем m запросов; в каждом заданы две вершины a и b, и нужно вывести, сколько вершин дерева равноудалены от a и от b (расстояние — число рёбер).

Формат ввода:

• Строка 1: число n ($1 \le n \le 10^5$).
• Каждая из следующих n − 1 строк: два числа — концы ребра.
• Далее строка с числом m ($1 \le m \le 10^5$).
• Каждая из следующих m строк: два числа a и b.

Формат вывода: m строк, в каждой ответ на очередной запрос.

Пример 1:

Ввод:
4
1 2
1 3
2 4
1
2 3

Вывод:
1

Пример 2:

Ввод:
4
1 2
2 3
2 4
2
1 2
1 3

Вывод:
0
2

Разберём на примере

Возьмём второй пример: вершина 2 соединена с 1, 3 и 4 — то есть 1, 3 и 4 висят на вершине 2.

Запрос 1 2. Расстояние между вершинами 1 и 2 равно 1 — нечётное. Проверим все вершины руками:

Ноль — и это не случайность. Для любой вершины v сумма расстояний до a и до b имеет ту же чётность, что и расстояние между a и b. Если бы расстояния до a и до b совпали, сумма была бы чётной — значит и расстояние между a и b обязано быть чётным. При нечётном ответ всегда ноль, дерево смотреть не нужно.

Запрос 1 3. Расстояние равно 2, путь 1 — 2 — 3. Считаем:

Ответ 2 — вершины 2 и 4.

Теперь посмотрим, почему подошли именно они. Середина пути 1 — 2 — 3 — вершина 2. Вершина 4 «прицепляется» к пути тоже в вершине 2. А вершины 1 и 3 прицепляются к пути в себе самих. Отсюда общее правило: вершина равноудалена от a и b ровно тогда, когда она подходит к пути a–b в его середине.

Осталось понять, как такие вершины посчитать. Если из дерева убрать два ребра, выходящих из середины вдоль пути, дерево распадётся, и нужные нам вершины — это ровно кусок, оставшийся при середине. В нашем примере середина — вершина 2, убираем рёбра 2 — 1 и 2 — 3, остаётся кусок {2, 4} — два элемента.

Идея решения

Алгоритм в одну фразу: для каждого запроса найти общего предка, посчитать расстояние; при нечётном ответить нулём, иначе найти середину пути двоичными подъёмами и вернуть размер куска дерева, «висящего» при середине после удаления двух рёбер пути.

Почему совпадают именно вершины середины. Пусть v — произвольная вершина, и пусть p — вершина, в которой путь от v впервые попадает на путь a–b (такая вершина всегда одна). Тогда

$dist(v, a) = dist(v, p) + dist(p, a), \qquad dist(v, b) = dist(v, p) + dist(p, b)$

Слагаемое dist(v, p) одинаково, поэтому равенство расстояний равносильно dist(p, a) = dist(p, b). На пути a–b такая вершина p ровно одна — середина. Значит v подходит тогда и только тогда, когда её «точка входа» на путь — середина.

Как считать размер куска. Подвесим дерево за вершину 1 и посчитаем размеры поддеревьев. Дальше два случая.

Случай 1: a и b на одной глубине. Тогда середина пути — их общий предок l. Из него путь уходит вниз по двум разным дочерним вершинам: ca — в сторону a, cb — в сторону b. Убрав эти два ребра, мы отрезаем два поддерева, а всё остальное дерево остаётся при середине:

$\text{ответ} = n - size[ca] - size[cb]$

Случай 2: глубины разные. Пусть a глубже. Тогда середина c лежит строго ниже общего предка, на пути от a вверх. Из c путь уходит вверх (к предку) и вниз к дочерней вершине cc в сторону a. Убрав эти два ребра, при середине остаётся поддерево c без поддерева cc:

$\text{ответ} = size[c] - size[cc]$

Обе вершины — c и cc — это предки a на расстоянии h и h − 1, где h — половина расстояния; их и достаёт функция подъёма.

Отдельный случай a = b. Тогда равноудалены все n вершин — расстояние до обеих одно и то же по определению. Формулы выше на этот случай не рассчитаны, его надо обработать явно.

Почему не подойдёт обход на каждый запрос. Сто тысяч запросов по сто тысяч вершин — $10^{10}$ операций.

Псевдокод

построить дерево, подвесить за 1
обходом посчитать depth[v], up[0][v], порядок обхода
заполнить таблицу up[k][v] = up[k-1][up[k-1][v]]
обратным проходом посчитать size[v]

для каждого запроса (a, b):
    если a == b: вывести n; продолжить
    l = lca(a, b)
    d = depth[a] + depth[b] - 2 * depth[l]
    если d нечётно: вывести 0; продолжить
    h = d / 2
    если depth[a] == depth[b]:
        ca = предок(a, h - 1)              // дочерняя вершина l в сторону a
        cb = предок(b, h - 1)              // дочерняя вершина l в сторону b
        вывести n - size[ca] - size[cb]
    иначе:
        если depth[a] < depth[b]: поменять a и b местами
        c  = предок(a, h)                  // середина пути
        cc = предок(a, h - 1)              // её дочерняя вершина в сторону a
        вывести size[c] - size[cc]

Код решения

Комментарии по реализации. Присваивание up[0][1] = 1 делается после обхода, а не до: во время обхода этот элемент всё равно не читается, зато после него любой подъём из корня безопасно остаётся в корне и не выходит за пределы дерева. Размеры поддеревьев считаются обратным проходом по массиву order — тем же, что заполнил обход, без второго прохода по графу. Ответ может достигать n, но в 32-битный тип помещается спокойно; 64-битный тип в C++ взят только чтобы не думать о знаках в выражении n - sz[ca] - sz[cb]. Вывод собирается в одну строку: сто тысяч отдельных печатей — заметная доля времени.

Проверка на примерах

Пример 2, запрос 1 2. Общий предок — вершина 1, расстояние $0 + 1 - 0 = 1$, нечётное. Ответ 0.

Пример 2, запрос 1 3. Подвесим за 1: depth[1] = 0, depth[2] = 1, depth[3] = depth[4] = 2; размеры — size[1] = 4, size[2] = 3, size[3] = size[4] = 1. Общий предок 1 и 3 — вершина 1, расстояние 2, h = 1. Глубины разные, глубже вершина 3. Середина — предок вершины 3 на расстоянии 1, то есть вершина 2; её дочерняя вершина в сторону 3 — предок на расстоянии 0, то есть сама вершина 3. Ответ $size[2] - size[3] = 3 - 1 = 2$. Совпадает и с ручным перебором в разборе выше. Наш вывод: 0 и 2 — совпадает с ожидаемым.

Пример 1. Дерево: 1 соединена с 2 и 3, к вершине 2 подвешена 4. Запрос 2 3: общий предок — вершина 1, глубины равны единице, расстояние 2, h = 1. Дочерняя вершина общего предка в сторону 2 — это сама вершина 2 (предок на расстоянии 0), в сторону 3 — вершина 3. Ответ $4 - size[2] - size[3] = 4 - 2 - 1 = 1$. Проверим руками: подходит только вершина 1 (расстояние 1 до обеих); вершина 4 на расстоянии 1 от 2 и 3 от 3 — не подходит. Наш вывод: 1 — совпадает с ожидаемым.

Крайние случаи

• a = b. Ответ n; формулы через середину пути этот случай не покрывают, нужна отдельная ветка.
• n = 1. Дерево из одной вершины, любой запрос — это a = b, ответ 1.
• Нечётное расстояние. Ответ 0 без всякой работы с деревом — самая частая ветка на случайных тестах.
• a — предок b. Тогда общий предок совпадает с a, и разбор идёт по второй ветке; проверка того, что подъёмы не «перепрыгивают» через общего предка.
• Дерево-цепочка на $10^5$ вершин. Максимальная глубина: тест на нерекурсивный обход и на достаточный размер LOG.
• Звезда. Все листья на одной глубине, все запросы между листьями идут по первой ветке; ответ $n - 1 - 1 = n - 2$.
• Середина пути — сама вершина a. Возможно, когда a — предок b ровно на середине; проверка того, что anc(a, 0) возвращает саму вершину.

Типичные ошибки

1. Обходить дерево на каждый запрос. $10^{10}$ операций.
2. Забыть проверку на нечётность. Формулы через середину при нечётном расстоянии выдадут мусор, а не ноль.
3. Не обработать a = b. Расстояние ноль, h = 0, и подъём на h − 1 уводит в отрицательные значения.
4. Перепутать порядок циклов при построении таблицы. Если внешним сделать цикл по вершинам, up[k-1] для нужной вершины ещё не посчитан.
5. Не задать up[0][root] = root. Тогда подъём из корня уходит в вершину 0 и портит сравнения в LCA.
6. Прыгать в LCA, пока предки совпадают. Условие ровно обратное: прыгаем, только пока предки различаются.
7. Считать LOG как log2(n) без округления вверх. На $n = 10^5$ не хватит одного уровня, и глубокие подъёмы сломаются.
8. Взять размеры поддеревьев до подвешивания. Размер зависит от корня; считать его надо после того, как выбран корень 1.

Сложность

Время: $O(n\log n)$ на предпосчёт и $O(\log n)$ на запрос, итого $O((n + m)\log n)$. Память: $O(n\log n)$ на таблицу подъёмов.

---

Задача 2 — CF ~2100 — «Minimum spanning tree for each edge»

Что дано

Дан связный неориентированный взвешенный граф из n вершин и m рёбер. Для каждого ребра нужно вывести минимальный возможный вес остовного дерева, которое обязано содержать это ребро.

Формат ввода:

• Строка 1: два числа n и m ($1 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$).
• Каждая из следующих m строк: три числа u, v, w — концы ребра и его вес ($1 \le w \le 10^9$).

Формат вывода: m строк — ответы в том же порядке, в каком рёбра заданы во вводе.

Пример:

Ввод:
5 7
1 2 3
1 3 1
1 4 5
2 3 2
2 5 3
3 4 2
4 5 4

Вывод:
9
8
11
8
8
8
9

Разберём на примере

Сначала построим минимальный остов Краскалом — рёбра в порядке возрастания веса, берём, если концы ещё не связаны:

Остов: рёбра 1—3 (1), 2—3 (2), 3—4 (2), 2—5 (3). Его вес $W = 8$.

Четыре ребра из семи попали в остов — для них ответ просто 8: дешевле остова с обязательным ребром, которое и так в нём есть, ничего не бывает.

Остаются три ребра. Возьмём 1 — 4 весом 5. Путь между вершинами 1 и 4 внутри остова: 1 — 3 (вес 1) и 3 — 4 (вес 2), максимум равен 2. Добавляем ребро 1—4 — получается цикл 1 — 3 — 4 — 1. Чтобы вернуть дерево, убираем из цикла самое тяжёлое ребро, кроме обязательного, то есть ребро веса 2:

$8 + 5 - 2 = 11$

Совпадает с третьим числом ожидаемого вывода.

Аналогично для 1 — 2 весом 3: путь 1 — 3 — 2 с весами 1 и 2, максимум 2, ответ $8 + 3 - 2 = 9$. И для 4 — 5 весом 4: путь 4 — 3 — 2 — 5 с весами 2, 2, 3, максимум 3, ответ $8 + 4 - 3 = 9$.

Обратите внимание, зачем выкидывается именно самое тяжёлое ребро пути: любое ребро цикла годится для восстановления дерева, но чем тяжелее выброшенное, тем дешевле результат.

Идея решения

Алгоритм в одну фразу: построить минимальный остов Краскалом, построить на нём таблицу двоичных подъёмов с максимумом веса ребра, и для каждого ребра выдать либо вес остова (если ребро в остове), либо вес остова плюс вес ребра минус максимум на пути между его концами.

Почему конструкция даёт остов. Добавление ребра (u, v) к дереву создаёт ровно один цикл — само ребро плюс единственный путь от u до v в дереве. Удаление любого ребра этого цикла снова даёт связный граф без циклов на всех n вершинах, то есть остов. Мы удаляем самое тяжёлое ребро пути и получаем вес $W + w - M$.

Почему дешевле не бывает. Мысленно запустим Краскала заново, но объявим концы e заранее соединёнными, а само e — уже взятым бесплатно. Алгоритм пойдёт по тем же рёбрам в том же порядке и примет те же решения, кроме одного момента: рёбра пути между u и v шли бы в остов как обычно, но самое тяжёлое из них к своей очереди окажется лишним — его концы уже связаны остальными рёбрами того же пути плюс бесплатным e. Значит из старого набора выпадет ровно одно ребро, и это именно $M$. Итоговый вес — $W + w - M$, и он минимален, потому что Краскал строит минимальный остов.

Почему для рёбер остова ответ равен $W$. Минимальный остов — минимальный среди всех; если требуемое ребро уже в нём, ограничение ничего не запрещает.

Как считать максимум на пути. Той же таблицей двоичных подъёмов, что и LCA, только рядом с up[k][v] кладём mx[k][v] — максимальный вес ребра на подъёме от v на $2^k$ уровней. Склейка очевидна: максимум на подъёме из двух половин — максимум из двух половинных максимумов.

Про типы. Двести тысяч рёбер весом до $10^9$ дают вес остова до $2 \cdot 10^{14}$ — 64-битный тип обязателен.

Псевдокод

прочитать все рёбра
отсортировать индексы рёбер по весу
Краскал через СНМ:
    если концы в разных компонентах: объединить, пометить ребро как остовное,
                                      добавить в списки смежности остова, W += вес

обойти остов из вершины 1, посчитать depth[v], up[0][v], mx[0][v]
заполнить таблицы up[k][v] и mx[k][v]

для каждого ребра i (в исходном порядке):
    если ребро остовное: вывести W
    иначе: вывести W + вес[i] - максимум_на_пути(u[i], v[i])

Код решения

Комментарии по реализации. Сортируются не сами рёбра, а их индексы: ответы нужно выдать в исходном порядке ввода, и перестановка рёбер этот порядок сломала бы. Списки смежности строятся только из рёбер остова — по остальным ходить незачем, и это заодно гарантирует, что обход даёт дерево, а не граф с циклами. Вес остова накапливается в 64-битном типе, а сама таблица mx остаётся 32-битной: там лежат веса отдельных рёбер, до $10^9$. Проверка if u == v: return res в середине функции обязательна — это случай, когда одна вершина оказалась предком другой, и второй цикл в нём просто не нужен.

Проверка на примерах

Пример из условия. Остов и его вес посчитаны в разборе выше: $W = 8$. Сводим всё в таблицу:

Наш вывод: 9 8 11 8 8 8 9 по строкам — совпадает с ожидаемым.

Прогоним ещё два случая, которых в условии нет:

Ввод:
2 1
1 2 7

Вывод:
7

Единственное ребро обязано войти в остов; вес остова равен 7.

Ввод:
3 3
1 2 1
2 3 1
1 3 100

Вывод:
2
2
101

Остов — два ребра веса 1, его вес 2. Для тяжёлого ребра: путь между 1 и 3 состоит из двух рёбер веса 1, максимум 1, ответ $2 + 100 - 1 = 101$.

Крайние случаи

• m = n − 1. Граф сам является деревом; все рёбра в остове, все ответы равны $W$.
• n = 1. Вершина одна, рёбер нет — выводить нечего; код не должен падать на пустом цикле.
• n = 2. Один или несколько параллельных рёбер между двумя вершинами: в остов войдёт самое лёгкое, для остальных путь состоит ровно из одного ребра.
• Кратные рёбра одинакового веса. В остов попадёт первое встреченное, для остальных ответ будет тем же числом $W$ — потому что $w = M$ и поправка нулевая.
• Все веса равны. Любое ребро вне остова даёт поправку ноль, все ответы совпадают с $W$.
• Максимальный вес. $2 \cdot 10^5$ рёбер по $10^9$ — до $2 \cdot 10^{14}$, 64-битный тип.
• Граф-цепочка на $2 \cdot 10^5$ вершин плюс одно длинное ребро. Максимальная глубина подъёмов: тест на нерекурсивный обход и на размер LOG.

Типичные ошибки

1. Перестраивать остов для каждого ребра. $m$ запусков Краскала — $4 \cdot 10^{10}$ операций.
2. Сортировать сами рёбра, а не индексы. Ответы требуется выдать в порядке ввода.
3. Забыть про рёбра, уже вошедшие в остов. Для них ответ $W$, а формула с максимумом на пути дала бы $W + w - w = W$ только случайно — путь между концами такого ребра состоит из него самого, и это верно лишь если реализация это учитывает.
4. Считать вес остова в 32-битном типе. До $2 \cdot 10^{14}$.
5. Строить подъёмы по всему графу, а не по остову. Таблица подъёмов определена только для дерева.
6. Пропустить последний шаг в максимуме на пути. После синхронного подъёма остаются два ребра до общего предка, и их надо добавить в максимум явно.
7. Считать, что выкидывать надо ребро минимального веса. Наоборот: чем тяжелее выброшенное ребро, тем дешевле остов.
8. Рекурсивный обход остова. Цепочка из $2 \cdot 10^5$ вершин.

Сложность

Время: $O(m\log m)$ на сортировку и Краскала, $O(n\log n)$ на таблицы подъёмов, $O(\log n)$ на ребро — итого $O((n + m)\log n)$. Память: $O(n\log n)$.

---

Самостоятельная тренировка

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

• Codeforces 191C «Fools and Roads» (~CF 1900) — по дереву проходит k маршрутов, каждый задан парой вершин; нужно для каждого ребра узнать, сколько маршрутов по нему прошло. Подсказка: прибавление единицы на всём пути делается тремя правками в вершинах — по единице на концах и минус два в их общем предке, — после чего один обход снизу вверх собирает ответы.
• Codeforces 1304E «1-Trees and Queries» (~CF 2000) — дано дерево и запросы вида «пять чисел x, y, a, b, k»: если временно добавить к дереву ребро между x и y, существует ли маршрут из a в b длиной ровно k рёбер (по рёбрам ходить можно сколько угодно раз)? Подсказка: маршрут длины k существует тогда, когда есть путь длины d с d ≤ k и совпадающей с k чётностью — лишние шаги всегда можно «съесть», походив по ребру туда-обратно; кандидатов на d всего три, и все три считаются расстояниями через общего предка.
• Codeforces 1702G2 «Passable Paths (hard version)» (~CF 2000) — для каждого запроса дан набор вершин; нужно проверить, лежат ли все они на одном простом пути дерева. Подсказка: найдите две «крайние» вершины набора и проверьте, что каждая из остальных лежит на пути между ними, — а «лежит на пути» проверяется через расстояния и общего предка.
• Codeforces 733F «Drivers Dissatisfaction» (~CF 2200) — у рёбер есть вес и цена уменьшения; на суммарный бюджет надо снизить веса нескольких рёбер так, чтобы минимальный остов получился как можно легче. Прямое продолжение сегодняшней второй задачи: снова остов строится один раз, а для каждого ребра считается, что произойдёт, если вставить его силой.

Прорешай их самостоятельно — если застрянешь, разбери с AI-партнёром на codepal.ru: он не даёт готовый ответ, а подводит к решению вопросами.

---

Что дальше

Сегодняшняя тренировка была про то, что на «Пике» половина решения — это уже написанная заготовка. Таблица двоичных подъёмов встретится ещё не раз; если сейчас она собиралась по кусочкам из объяснения, самое полезное действие — сесть и написать её с нуля по памяти, вместе с подъёмом на k уровней, общим предком и максимумом на пути. Двадцать минут сейчас экономят полчаса на каждом следующем контесте.

На предпоследней тренировке цикла — приём про то, как обойти дерево «почти за линию» там, где наивно получается квадрат: слияние множеств от меньшего к большему. Это тот редкий случай, когда оценка сложности сама подсказывает алгоритм.