Тренировочная сессия 22: слияние от меньшего к большему СЕССИЯ

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

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

Приём — слияние от меньшего к большему (в англоязычных разборах — small-to-large merging, иногда «DSU on tree»). Ситуация: для каждой вершины дерева нужен ответ по её поддереву, и ответ требует хранить не одно число, а целое распределение — счётчики цветов, глубин, значений. Свернуть распределение в число заранее нельзя. Наивно — на каждую вершину строить свой словарь, копируя структуры потомков: это квадрат. Приём же выглядит как «жульничество»: не создавать новый словарь, а забрать словарь самого крупного потомка и влить в него остальные. Работает это за $O(n\log n)$, и доказательство занимает три строки.

Обе задачи на него, различаются только структуры и вопросы. В первой это счётчики цветов и вопрос «какие цвета встречаются чаще всего в поддереве». Во второй — словарь «глубина → множество имён» и запросы к отдельным слоям поддерева; заодно там появится офлайн-обработка запросов, без которой приём вообще не применить к задачам с запросами.

---

Теория

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

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

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

• ответ нужен для каждой вершины по её поддереву;
• ответ зависит от распределения (сколько раз встречается каждый цвет, каждая глубина, каждое значение), а не от сворачиваемой величины вроде суммы или максимума;
• $n$ до $10^5$–$2 \cdot 10^5$, то есть квадрат не проходит.

Как решать:

1. Обойти дерево, получить порядок обхода и предков; дальше работать в обратном порядке — дочерние вершины раньше предков.
2. Для вершины v найти дочернюю вершину с наибольшей структурой и забрать её себе целиком, за одну операцию (обмен ссылками, а не копирование).
3. Вливать в неё структуры остальных дочерних вершин поэлементно, попутно обновляя ответ, и освобождать их.
4. Добавить собственный вклад вершины v и записать ответ.

Почему это быстро. Посмотрим на один элемент и посчитаем, сколько раз он может «переехать». Переезд происходит только тогда, когда элемент был в не самой большой структуре — то есть переезжает он в структуру, размер которой минимум вдвое больше его прежней. Удвоение можно повторить не более $\log_2 n$ раз. Значит на каждый элемент приходится не более логарифма переездов, а всего переездов — $O(n\log n)$.

Мини-пример. У вершины три дочерние вершины со словарями размеров 100, 3 и 1. Наивный подход создаёт новый словарь и копирует все 104 элемента. Приём забирает словарь на 100 элементов бесплатно и переносит только 4. Разница ровно в том, что сотня элементов не тронута — и именно это повторяется на каждом уровне.

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

Сложность приёма: $O(n\log n)$ операций слияния (плюс стоимость самой структуры — с обычным словарём это и есть итог, с деревом множеств будет $O(n\log^2 n)$).

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

Почему это работает — оценка, которую стоит уметь воспроизводить. Рассуждение ведётся не «сверху», от структуры дерева, а «снизу», от отдельного элемента. Проследим за одним элементом: он лежит в какой-то структуре, и переезжает он только тогда, когда его структура оказалась не больше той, в которую вливается. Значит после переезда размер структуры, где он лежит, как минимум удвоился. Удвоиться от единицы до n можно не больше $\log_2 n$ раз — вот и весь ответ: каждый элемент переезжает не больше логарифма раз, суммарно $O(n\log n)$ переездов.

Обратите внимание, что в оценке нигде не участвует форма дерева. Она одинаково верна и для цепочки, и для звезды, и для случайного дерева — в этом её сила и в этом же причина, почему приём так часто оказывается достаточным там, где кажется, что нужна тяжёлая структура.

Что должно выполняться, чтобы приём был применим. Три условия, и все три стоит проверять до кода:

1. Ответ для вершины собирается из ответов потомков плюс сама вершина — то есть задача действительно про поддеревья, а не про пути или про всё дерево сразу.
2. Информацию о поддереве нельзя свернуть в одно-два числа. Если можно — приём избыточен: хватит обычной динамики по поддеревьям за линию. Small-to-large нужен ровно тогда, когда приходится тащить наверх целое распределение: счётчики цветов, множество имён, набор глубин.
3. Структуру можно сливать, не разбирая. Слияние обязано стоить порядка размера меньшей структуры. Словари, множества, счётчики — годятся; отсортированные массивы, которые надо пересобирать целиком, — нет.

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

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

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

Сложность приёма: $O(n\log n)$ слияний; если операция слияния сама не константная (например, элементы кладутся в сбалансированное дерево), добавляется ещё один логарифм.

---

Задача 1 — CF ~2300 — «Lomsat gelral»

Что дано

Дано дерево из n вершин, подвешенное за вершину 1. Каждая вершина покрашена в некоторый цвет.

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

Для каждой вершины нужно вывести сумму всех доминирующих цветов её поддерева.

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

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

Формат вывода: n чисел — ответы для вершин от 1 до n.

Пример 1:

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

Вывод:
10 9 3 4

Пример 2:

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

Вывод:
3 6 2 2 3

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

Первый пример прозрачен: все четыре цвета разные, поэтому в любом поддереве каждый цвет встречается ровно один раз и доминируют все. Ответ для вершины — просто сумма цветов её поддерева: для листьев 3 и 4 это 3 и 4, для вершины 2 это $2 + 3 + 4 = 9$, для корня $1 + 2 + 3 + 4 = 10$.

Второй пример интереснее. Дерево: к корню 1 подвешены вершины 2 и 3, к вершине 2 — вершины 4 и 5. Цвета: у вершин 1 и 2 цвет 1, у вершин 3 и 4 цвет 2, у вершины 5 цвет 3.

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

Теперь — почему наивное решение не проходит. Для каждой вершины нужен свой набор счётчиков, и если строить его копированием структур дочерних вершин, то на «гребёнке» (длинная цепочка с листом на каждом шаге) корневой словарь будет собираться заново на каждом уровне: $n/2$ уровней по $n/2$ элементов — квадрат, $2.5 \cdot 10^9$ операций на $n = 10^5$.

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

Идея решения

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

Почему такое слияние даёт $O(n\log n)$. Проследим за одной вершиной дерева как за элементом словаря. Она меняет словарь только тогда, когда её словарь оказался не самым крупным среди дочерних вершин. Значит новый словарь содержит как минимум столько же элементов, сколько старый, плюс элементы самой крупной дочерней вершины — то есть его размер минимум вдвое больше. Удвоений от 1 до $n$ бывает не больше $\log_2 n$, значит одна вершина переезжает не более $\log_2 n$ раз, а всего переносов — $O(n\log n)$.

Почему максимум и сумму можно поддерживать по ходу. Счётчики только растут. Когда счётчик цвета c стал равен nk:

• если nk больше текущего максимума — этот цвет теперь единственный доминирующий, максимум становится nk, сумма — c;
• если nk равен максимуму — цвет добавляется к уже доминирующим, сумма увеличивается на c;
• если меньше — ничего не меняется.

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

Про типы. Цвета до $10^5$, доминирующих может быть до $10^5$ штук — сумма доходит до $5 \cdot 10^9$. 32-битный тип переполняется.

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

Псевдокод

обойти дерево из вершины 1 нерекурсивно, запомнив порядок и предков

для v в обратном порядке обхода:
    big = дочерняя вершина v с самым большим словарём (или «нет»)
    если big == «нет»:
        d = пустой словарь; макс = 0; сумма = 0
    иначе:
        d, макс, сумма = структура big        // забрали целиком
        освободить структуру big

    для каждой другой дочерней вершины to:
        для (цвет, k) в словаре to:
            nk = d[цвет] + k
            d[цвет] = nk
            если nk > макс: макс = nk; сумма = цвет
            иначе если nk == макс: сумма += цвет
        освободить структуру to

    nk = d[цвет(v)] + 1
    d[цвет(v)] = nk
    если nk > макс: макс = nk; сумма = цвет(v)
    иначе если nk == макс: сумма += цвет(v)

    ответ[v] = сумма
    структура v = (d, макс, сумма)

вывести ответ[1..n]

Код решения

Комментарии по реализации. Ключевая строка в C++ — mp[v].swap(mp[big]): обмен внутренностями двух контейнеров стоит константу независимо от их размера, и именно он делает приём работающим. Освобождение памяти через unordered_map<int,int>().swap(...) не косметика: без него на $10^5$ вершинах в памяти одновременно висят все словари, а с ним — только «живые» ветки. В Python роль обмена играет присваивание ссылки d = cnt[big], а роль освобождения — cnt[big] = None; словарь при этом не копируется ни разу. Максимальный счётчик и сумма хранятся рядом со словарём и переезжают вместе с ним — пересчитывать их после слияния было бы линейно по размеру и убило бы всю экономию.

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

Пример 1. Все цвета разные, значит любой счётчик равен единице, максимум равен единице во всех поддеревьях, и сумма доминирующих — это сумма цветов поддерева. Для вершин 3 и 4 — 3 и 4; для вершины 2 — $2 + 3 + 4 = 9$; для вершины 1 — $1 + 2 + 3 + 4 = 10$. Наш вывод: 10 9 3 4 — совпадает с ожидаемым.

Пример 2. Проследим слияние в вершине 1. Её дочерние вершины — вершина 2 (словарь {1:1, 2:1, 3:1}, максимум 1, сумма 6) и вершина 3 (словарь {2:1}, максимум 1, сумма 2).

Ответ корня — 3. Вместе с посчитанными ранее ответами остальных вершин получаем 3 6 2 2 3. Наш вывод совпадает с ожидаемым.

Отдельно стоит проследить шаг 2: цвет 2 обогнал максимум, поэтому сумма перезаписалась на 2, а не увеличилась. И шаг 3: цвет 1 сравнялся с максимумом, поэтому сумма увеличилась. Именно эти две ветки чаще всего путают местами.

Проверим ещё вырожденный вход:

Ввод:
1
5

Вывод:
5

Одна вершина, один цвет — он и доминирующий.

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

• n = 1. Рёбер нет, цикл чтения рёбер не выполняется; ответ — единственный цвет.
• Все цвета одинаковы. В каждом поддереве доминирующий один, ответ для вершины — сам цвет, независимо от размера поддерева.
• Все цвета различны. Ответ для вершины — сумма цветов её поддерева; максимальная нагрузка на сумму (до $5 \cdot 10^9$).
• Дерево-цепочка на $10^5$ вершин. Проверка того, что обход нерекурсивный, а слияния не превращаются в квадрат.
• «Гребёнка» — цепочка, к каждой вершине которой подвешен лист. Худший случай для наивного копирования и типовой тест на правильность выбора «самой крупной дочерней вершины».
• Ровно два доминирующих цвета. Проверка ветки «счётчик сравнялся с максимумом» — самая частая точка отказа.

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

1. Создавать новый словарь на каждой вершине. Ровно тот квадрат, ради ухода от которого приём и существует.
2. Выбирать «самую крупную дочернюю вершину» по размеру поддерева, а не по размеру словаря. Обычно это одно и то же по порядку величины, но оценка $O(n\log n)$ доказана именно для размера структуры; при хитрых структурах эти величины расходятся.
3. Пересчитывать максимум и сумму после слияния. Проход по объединённому словарю линеен по его размеру — экономия от приёма исчезает полностью.
4. Перепутать ветки «больше» и «равно». При строгом превышении сумма перезаписывается, при равенстве — увеличивается.
5. Считать сумму в 32-битном типе. До $5 \cdot 10^9$.
6. Не освобождать словари дочерних вершин. На $10^5$ вершинах это лишние сотни мегабайт.
7. Рекурсивный обход. Цепочка из $10^5$ вершин кладёт стек.
8. Забыть добавить собственный цвет вершины. Легко теряется среди слияний, а проявляется только на тестах, где вершина не лист.

Сложность

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

---

Задача 2 — CF ~2400 — «Blood Cousins Return»

Что дано

Дано n человек, пронумерованных от 1 до n. У каждого есть имя и не более одного непосредственного предка — то есть перед нами лес: несколько деревьев, у которых корни это люди без предка.

Человек a называется k-потомком человека b, если, поднимаясь от a ровно k шагов вверх по предкам, мы попадаем в b. Дано m запросов вида «вершина v, число k»: нужно ответить, сколько различных имён встречается среди всех k-потомков v.

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

• Строка 1: целое n ($1 \le n \le 10^5$).
• Далее n строк: имя s (до 20 строчных латинских букв) и число r ($0 \le r \le n$) — номер непосредственного предка либо 0, если его нет.
• Далее строка с целым m ($1 \le m \le 10^5$).
• Далее m строк: два числа v и k ($1 \le v, k \le n$).

Формат вывода: m чисел — ответы на запросы в порядке их следования.

Пример 1:

Ввод:
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1

Вывод:
2
2
0
1
0

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

Разложим дерево из примера. У человека 1 (pasha) нет предка — это корень. Его непосредственные потомки: 2 (gerald), 3 (gerald) и 6 (olesya). У 2 есть потомок 4 (valera), у 3 — потомок 5 (igor).

Теперь запросы.

• 1 1 — потомки первого на расстоянии один: это 2, 3 и 6, с именами gerald, gerald, olesya. Различных имён два.
• 1 2 — на расстоянии два: 4 (valera) и 5 (igor). Различных имён два.
• 1 3 — на расстоянии три никого нет, ответ 0.
• 3 1 — у третьего один потомок, 5 (igor), ответ 1.
• 6 1 — у шестого потомков нет, ответ 0.

Первое, что стоит заметить: «k-потомки вершины v» — это в точности вершины её поддерева, находящиеся на глубине depth[v] + k, если глубину отсчитывать от корня. Переход от относительной глубины к абсолютной убирает из задачи всю рекурсию: запрос превращается в «сколько различных имён на такой-то абсолютной глубине внутри такого-то поддерева».

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

Какую именно информацию? Для ответа хватает словаря «глубина → множество имён, встречающихся на этой глубине в поддереве». Тогда запрос — это одно обращение к словарю и один len.

Осталась главная трудность: такой словарь для вершины собирается из словарей её потомков, а копировать их — тот самый квадрат, которого мы избегаем. Здесь и работает приём сессии: словарь самого крупного потомка забираем как есть, не копируя, и вливаем в него остальные. Каждое имя переезжает только в структуру, которая как минимум вдвое больше той, где оно лежало, — значит переездов у него не больше логарифма.

Идея решения

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

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

Почему словарь именно «глубина → множество». Нам нужны различные имена, то есть множество; а срез по глубине нужен потому, что запрос спрашивает не про всё поддерево, а про один его слой. Никакой другой информации не требуется, и это важно: чем меньше данных в структуре, тем дешевле слияние.

Почему абсолютная глубина, а не относительная. Если хранить глубину относительно текущей вершины, то при переходе к предку все ключи словаря сдвинулись бы на единицу — то есть словарь пришлось бы перестраивать целиком, и весь выигрыш пропал бы. С абсолютной глубиной ключи не меняются никогда, а запрос просто пересчитывается в depth[v] + k.

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

Псевдокод

прочитать имена и предков, построить списки потомков и список корней
прочитать запросы, разложить их по вершинам: queries[v] += (k, номер)

посчитать глубины обходом от каждого корня, запомнив порядок обхода

для v в обратном порядке обхода:          // потомки уже обработаны
    big = потомок с самым большим словарём (или «нет»)
    cur = словарь big, забранный как есть  // не копируем!
    для каждого другого потомка u:
        для каждой пары (глубина, множество имён) из словаря u:
            влить множество в cur[глубина]
    влить имя самой v в cur[depth[v]]

    для каждого запроса (k, номер) вершины v:
        ответ[номер] = размер cur[depth[v] + k], либо 0

    словарь[v] = cur

Код решения

Комментарии по реализации. Имена сразу заменяются номерами: сравнивать и хранить целые числа дешевле, чем строки до двадцати символов, а на множествах строк это чувствуется. Обход написан явным стеком — лес из $10^5$ вершин запросто оказывается цепочкой. Словари хранятся по ссылке (в C++ — указателем), и это принципиально: если крупнейшего потомка копировать, а не забирать, приём мгновенно превращается в квадрат, хотя код выглядит почти так же. Наконец, размер словаря поддерживается счётчиком, а не пересчитывается: выбор «самого крупного» происходит на каждой вершине, и обход всех пар ради размера съел бы весь выигрыш.

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

Пример 1: дерево из разбора. Глубины: у вершины 1 — 0; у 2, 3, 6 — 1; у 4 и 5 — 2.

Обход идёт снизу вверх. Проследим, что накапливается:

Обратите внимание на строку вершины 1: имена gerald из вершин 2 и 3 попали в одно множество и схлопнулись в одно — ровно это и требуется, ведь считаются различные имена.

Наш вывод: 2 2 0 1 0 — совпадает с ожидаемым.

Пример 2 проверяет работу с лесом: там два корня — вершина 1 и вершина 4. Запрос 4 1 спрашивает про потомков четвёртой на расстоянии один: это 5 (valera) и 6 (kolya), ответ 2. Остальные запросы попадают либо на пустые слои, либо на одиночные вершины. Наш вывод: 1 0 0 0 2 0 0 — совпадает с ожидаемым.

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

• n = 1. Одна вершина без потомков; любой запрос даёт 0.
• Все вершины — корни (у всех предок 0). Лес из n деревьев по одной вершине, все ответы нулевые.
• Цепочка из $10^5$ вершин. Проверка на нерекурсивность обхода; слияний почти нет, каждый словарь передаётся вверх как есть.
• Все имена одинаковые. Множества схлопываются до одного элемента, ответы равны 0 или 1 — хорошая проверка того, что считаются именно различные имена, а не количество вершин.
• Запрос с k, выходящим за глубину дерева. Ключа в словаре нет, ответ 0 — обращение к словарю обязано это переживать, а не падать.
• Звезда: корень и $10^5 - 1$ потомков. Худший случай по числу слияний на одной вершине; проверка, что выбор крупнейшего сделан по счётчику, а не пересчётом.

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

1. Копировать словарь крупнейшего потомка. Единственная строка, отделяющая $O(n\log n)$ от $O(n^2)$; на маленьких тестах разницы не видно.
2. Хранить глубину относительно текущей вершины. При подъёме все ключи придётся сдвигать, и слияние перестанет быть дешёвым.
3. Отвечать на запросы после сборки всего дерева. К этому моменту словари потомков уже поглощены и разобрать их обратно нельзя; отвечать надо в момент обработки вершины.
4. Считать количество вершин вместо количества различных имён. Второй пример это ловит: у корня двое потомков с одинаковым именем.
5. Забыть, что это лес. Единственный корень не гарантирован; обход надо запускать из каждой вершины с нулевым предком.
6. Рекурсивный обход. Падение на цепочке при формально верном алгоритме.

Сложность

Время: $O(n\log n)$ на слияния плюс $O(m)$ на ответы — каждое имя переезжает не больше логарифма раз. Память: $O(n)$ — в сумме по всем живым словарям хранится не больше одной записи на вершину.

---

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

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

• Codeforces 1076E «Vasya and a Tree» (~CF 1900) — разминочная. Даны запросы «прибавить x всем вершинам поддерева v на глубине не больше d от него»; нужно вывести итоговые значения. Подсказка: структура здесь одномерная — массив «поправка по глубине», который живёт вдоль текущего пути обхода и откатывается при выходе из вершины.
• Codeforces 208E «Blood Cousins» (~CF 2100) — младший брат сегодняшней второй задачи: спрашивают не количество различных имён, а количество вершин на том же уровне с тем же предком. Полезно решить обе и сравнить, насколько похожими получились решения.
• Codeforces 570D «Tree Requests» (~CF 2200) — на каждой вершине написана буква; для запроса «вершина v, глубина h» нужно понять, можно ли переставить буквы всех вершин глубины h в поддереве v так, чтобы получился палиндром. Подсказка: палиндром возможен, когда букв нечётной кратности не больше одной, — а это одно число, если хранить чётности битовой маской.
• Codeforces 1009F «Dominant Indices» (~CF 2300) — для каждой вершины нужно найти такую глубину относительно неё, на которой в её поддереве лежит наибольшее количество вершин, а при нескольких таких — наименьшую. Подсказка: структура — счётчики «сколько вершин на каждой глубине», и сливается она ровно как сегодняшние счётчики цветов; существует и более быстрое решение через слияние массивов «по длинному пути», но начните с приёма этой сессии.

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

---

Что дальше

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

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