Тренировочная сессия 13: жадность на дереве СЕССИЯ

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

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

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

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

Обе задачи — коридор ~CF 1600. Обе про то, что основная работа делается на бумаге, а код после этого получается коротким.

---

Теория

Жадность на дереве. Общая идея одна: заменить выбор по всему дереву на локальное правило для каждой вершины и доказать, что от такой замены оптимум не теряется.

Форма 1 — свести к независимым слагаемым и отсортировать.

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

• надо выбрать ровно k вершин дерева (или отрезков, или объектов) так, чтобы максимизировать суммарную величину;
• выгода одной вершины зависит от того, что выбрано вокруг, — то есть «в лоб» слагаемые не независимы;
• размер дерева до $10^5$–$10^6$, перебор подмножеств исключён.

Схема рассуждения, которая почти всегда работает:

1. Доказать структурное свойство оптимума — обычно обменом. Типичные формулировки: «если выбрана вершина, то выбраны и все вершины её поддерева», «выгоднее брать более глубокие», «оптимальный набор непрерывен».
2. Переписать сумму, пользуясь этим свойством, так, чтобы вклад каждой вершины считался независимо от остальных.
3. Убедиться, что жадный выбор k лучших по этому вкладу автоматически сохраняет структурное свойство — иначе жадность даст набор, для которого формула вклада уже неверна.

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

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

Каркас приёма — после сведения от дерева остаётся сортировка:

Где ошибаются в узнавании: пытаются писать динамику по дереву там, где хватает сортировки. Динамика по поддеревьям с ограничением «выбрать k вершин» стоит $O(nk)$ и на $10^5$ вершинах не проходит; жадность после сведения — $O(n \log n)$.

Сложность приёма: один обход дерева $O(n)$ плюс сортировка $O(n \log n)$.

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

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

• в условии просят восстановить или подобрать значения вершин, а не выбрать подмножество;
• ограничения локальны: значение вершины связано только с предком и непосредственными потомками;
• целевая функция монотонна — сумму значений надо минимизировать или максимизировать, и «чем меньше каждое, тем лучше» (или наоборот).

Как решать:

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

Мини-пример: значения накапливаются по пути от корня, поэтому значение вершины обязано быть не меньше, чем у предка, и не больше, чем у любого потомка. У нашей вершины два потомка со значениями 7 и 9, у предка значение 4. Отрезок допустимого — от 4 до 7: больше семи нельзя, иначе потомок с семёркой окажется меньше своего предка. Потомков двое, коэффициент отрицательный — значит берём верхний край, 7. Собственный вклад вершины при этом 3, зато вклады обоих потомков падают: 0 и 2 вместо 3 и 5.

Куда двигаться — вверх или вниз по отрезку — определяется одним подсчётом, и его стоит делать явно, а не на глаз. Посмотрим, как меняется итог, если сдвинуть значение одной вершины на единицу. Обычно вклад вершины считается как разность с предком, поэтому её значение входит в итог дважды: со знаком плюс в собственном вкладе и со знаком минус во вкладе каждого из m потомков. Итоговый коэффициент — $1 - m$:

• m = 0 (потомков нет): коэффициент $+1$, значение выгодно уменьшать — берём нижний край отрезка, вклад вершины нулевой;
• m = 1: коэффициент 0, итог от выбора не зависит — можно брать любой край;
• $m \ge 2$: коэффициент отрицательный, значение выгодно увеличивать — берём верхний край, то есть самое жёсткое ограничение от потомков.

Отсюда и общее правило: не «взять минимум допустимого» вслепую, а выписать коэффициент и двигаться в выгодную сторону до упора. Заметьте, что при m = 1 выбор безразличен, поэтому одно и то же правило «упереться в потолок от потомков» одинаково годится и для $m = 1$, и для $m \ge 2$ — это позволяет не разделять случаи в коде.

Где приём перестаёт работать. Жадность на дереве живёт ровно до тех пор, пока выбор в вершине не влияет на выбор в далёких вершинах. Как только появляется ограничение вида «во всём поддереве выбрано не больше k» или «выбранные вершины не должны быть соседними, и при этом их ровно k», локальное правило перестаёт быть корректным: приходится хранить состояние и переходить к динамике по поддеревьям, где для каждой вершины считается таблица по числу выбранного. Стоит она $O(nk)$ и на $10^5$ вершинах уже не проходит — поэтому в задачах такого размера почти всегда ожидается именно жадность, и её надо искать.

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

Сложность приёма: один обход дерева $O(n)$, плюс сортировка $O(n \log n)$ там, где она нужна.

---

Задача 1 — CF ~1600 — «Linova and Kingdom»

Что дано

Дано дерево из n городов, подвешенное за город 1 — столицу. Ровно k городов нужно объявить промышленными, остальные становятся туристическими (столица тоже может стать промышленной).

Из каждого промышленного города в столицу отправляется посланник по единственному пути. Радость посланника равна количеству туристических городов на его пути (сам город отправления не считается, столица считается, если она туристическая).

Нужно максимизировать суммарную радость всех посланников.

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

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

Формат вывода: одно число — максимальная суммарная радость.

Пример 1:

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

Вывод:
7

Пример 2:

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

Вывод:
2

Пример 3:

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

Вывод:
9

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

Возьмём пример 2: дерево 1 → 2 → 4 и 1 → 3, выбрать надо один промышленный город.

Ответ 2 — выгоднее всего самый глубокий город. Это первое наблюдение: чем глубже город, тем длиннее путь, а значит тем больше туристических городов он может пройти.

Но глубина — не всё. Возьмём пример 1. Дерево: у столицы дочерние вершины 2, 3 и 4; у города 3 дочерние вершины 5 и 6; у города 4 дочерняя вершина 7. Выбрать надо четыре города. Кандидаты на глубине 3 — города 5, 6, 7, у каждого путь из двух туристических городов, если выше ничего не выбрано. Но как только мы выбираем ещё и город 3, радость посланников из 5 и 6 падает: город 3 стал промышленным и больше не считается.

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

Посчитаем для примера 1 обе величины: глубина (столица = 1) и размер поддерева:

Возьмём четыре наибольших значения: 2 + 2 + 2 + 1 = 7 — это города 5, 6, 7 и 2, и ровно такой ответ ожидается. Осталось понять, почему сумма этих величин и есть суммарная радость.

Идея решения

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

Почему это работает. Разберём в три шага.

Шаг 1. В оптимуме множество выбранных городов «замкнуто вниз»: если город выбран, то выбраны и все города его поддерева. Допустим, это не так: выбран город v, а какой-то его потомок u — нет. Перенесём промышленность с v на u. Путь из u в столицу содержит путь из v целиком плюс участок от u до v, значит радость нового посланника не меньше прежней. Остальным посланникам от этого только лучше: город v стал туристическим и теперь считается на их путях. Сумма не уменьшилась — значит существует оптимум с этим свойством.

Шаг 2. При таком множестве сумма распадается на независимые слагаемые. Радость посланника из города v — это число его предков минус число выбранных среди них: $(\text{глубина}_v - 1) - (\text{выбранных предков } v)$. Просуммируем по всем выбранным v и посчитаем вторую часть суммы иначе — не «сколько у каждого выбранных предков», а «у скольких выбранных вершин данная вершина является предком». Для замкнутого вниз множества все потомки выбранной вершины a тоже выбраны, значит их ровно $\text{размер}_a - 1$. Получаем

$\sum_{v \in S} \left[(\text{глубина}_v - 1) - (\text{размер}_v - 1)\right] = \sum_{v \in S} (\text{глубина}_v - \text{размер}_v)$

Слагаемые больше не зависят друг от друга — каждая вершина приносит своё фиксированное число.

Шаг 3. Жадность сохраняет структуру. Возьмём k вершин с наибольшими значениями. Не окажется ли среди них предка без потомка? Нет: для любой вершины u, дочерней по отношению к v, выполняется $\text{глубина}_u = \text{глубина}_v + 1$ и $\text{размер}_u \le \text{размер}_v - 1$, откуда значение у дочерней вершины минимум на 2 больше, чем у предка. Значит потомок всегда попадает в набор раньше предка, и выбранное множество автоматически замкнуто вниз — формула из шага 2 применима.

Псевдокод

прочитать n, k, рёбра; построить список смежности

// обход от корня: глубины и порядок вершин
глубина[1] = 1
обойти дерево из вершины 1 (нерекурсивно), запоминая порядок обхода и предков

// размеры поддеревьев — обратным проходом по порядку обхода
размер[v] = 1 для всех v
для v в обратном порядке обхода:
    если предок[v] != 0:
        размер[предок[v]] += размер[v]

значения = [ глубина[v] - размер[v] для всех v ]
отсортировать значения по убыванию

вывести сумму первых k значений

Код решения

Комментарии по реализации. Размеры поддеревьев считаются без второго обхода: порядок, в котором вершины снимались со стека, гарантирует, что каждый потомок стоит в нём позже своего предка, поэтому обратный проход по этому порядку накапливает размеры корректно. Ответ обязан быть 64-битным: до $2 \cdot 10^5$ слагаемых, каждое до $2 \cdot 10^5$ — сумма доходит до $4 \cdot 10^{10}$. Значения глубин и размеров помещаются в 32-битный тип.

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

Пример 1: таблица значений посчитана выше: [−6, 1, −1, 0, 2, 2, 2]. Отсортированные по убыванию: 2, 2, 2, 1, 0, −1, −6. Сумма первых k = 4: 2 + 2 + 2 + 1 = 7.

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

Пример 2: дерево 1 → 2 → 4, 1 → 3.

Наибольшее одно: 2. Наш вывод: 2 — совпадает с ожидаемым.

Пример 3: рёбра 7−5, 1−7, 6−1, 3−7, 8−3, 2−1, 4−5. Подвесив за 1, получаем: дочерние вершины столицы — 7, 6, 2; дочерние вершины 7 — 5 и 3; дочерняя вершина 5 — 4; дочерняя вершина 3 — 8.

Пять наибольших: 3, 3, 1, 1, 1 — сумма 9. Наш вывод: 9 — совпадает с ожидаемым.

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

• k = n − 1. Выбираются почти все города; значения предков сильно отрицательные, но выбирать всё равно приходится — сумма может быть небольшой.
• k = 1. Ответ — максимум по всем вершинам, то есть самая «выгодная» глубокая вершина с маленьким поддеревом.
• Дерево-звезда. У всех листьев значение 2 − 1 = 1, у центра 1 − n; ответ равен k.
• Дерево-цепочка. Значения растут вниз: у листа n − 1, у корня 1 − n. Ответ — сумма k последних.
• Столица попала в выбор. Возможно при большом k; формула это корректно учитывает (значение столицы 1 − n).
• Максимальный размер. $n = 2 \cdot 10^5$ в виде цепочки — тест на нерекурсивность обхода и на 64-битный ответ.

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

1. Сортировать только по глубине. Игнорирует «порчу» потомкам: город с большим поддеревом невыгоден, даже если он глубокий.
2. Считать глубину столицы нулём. Тогда формула сдвигается на единицу и ответ занижается ровно на k. Глубина здесь — количество городов на пути, включая сам город.
3. Писать динамику «выбрать k вершин в поддереве». $O(nk)$ — при $n = 2 \cdot 10^5$ безнадёжно, хотя на маленьких тестах работает.
4. Рекурсивный обход. Цепочка из $2 \cdot 10^5$ вершин кладёт рекурсию.
5. Считать ответ в 32-битном типе. Сумма доходит до $4 \cdot 10^{10}$.
6. Не проверить, что жадность сохраняет структуру. Без шага 3 доказательство неполное: формула для суммы верна только для замкнутых вниз множеств.

Сложность

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

---

Задача 2 — CF ~1600 — «Sum in the tree»

Что дано

Дано дерево с корнем в вершине 1. Изначально на каждой вершине v было написано целое неотрицательное число a[v]. По ним посчитали s[v] — сумму значений на пути от корня до вершины v включительно, и h[v] — глубину вершины (число вершин на пути от корня до неё, так что h[1] = 1).

Затем все a[v] стёрли, а заодно случайно стёрли и все s[v] для вершин чётной глубины: на их месте стоит −1. Нужно восстановить значения a[v] так, чтобы они были неотрицательными и согласованными с оставшимися s[v], а суммарное значение по всем вершинам оказалось минимальным. Если восстановить невозможно — вывести −1.

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

• Строка 1: целое n ($2 \le n \le 10^5$) — количество вершин.
• Строка 2: числа p[2] … p[n] ($1 \le p_i < i$) — предок каждой вершины, начиная со второй.
• Строка 3: числа s[1] … s[n] ($-1 \le s_v \le 10^9$), где стёртые значения заменены на −1.

Формат вывода: минимальная суммарная сумма всех a[v], либо −1, если такого дерева не существует.

Пример 1:

Ввод:
5
1 1 1 1
1 -1 -1 -1 -1

Вывод:
1

Пример 2:

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

Вывод:
2

Пример 3:

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

Вывод:
-1

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

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

$a[v] = s[v] - s[p(v)], \qquad a[1] = s[1]$

Значит требование «все a[v] неотрицательны» — это в точности «s не убывает вниз по дереву», а суммарный ответ равен сумме всех этих разностей плюс s[1].

Возьмём пример 2: n = 5, предки p[2] = 1, p[3] = 2, p[4] = 3, p[5] = 1, известные суммы s = [1, −1, 2, −1, −1].

Глубины: у корня 1, у вершин 2 и 5 — глубина 2, у вершины 3 — глубина 3, у вершины 4 — глубина 4. Стёрты значения на чётных глубинах, то есть у вершин 2, 4 и 5 — сходится с тем, что в них стоит −1.

Теперь восстановим стёртое.

• Вершина 5 — стёрта, потомков нет. Её значение снизу подпирает предок (s[5] \ge s[1] = 1), а сверху не подпирает ничто. Коэффициент из теории при нуле потомков равен $+1$, то есть значение выгодно уменьшать: берём s[5] = 1, и a[5] = 0.
• Вершина 4 — тоже стёрта и тоже без потомков: s[4] = s[3] = 2, a[4] = 0.
• Вершина 2 — стёрта, но у неё есть потомок: вершина 3 со значением s[3] = 2. Сверху её подпирает эта двойка (s[2] \le 2), снизу — корень (s[2] \ge 1). Потомок один, коэффициент нулевой — итог от выбора не зависит, но правило «упереться в потолок от потомков» даёт s[2] = 2.

Теперь считаем ответ: a[1] = 1, a[2] = 2 − 1 = 1, a[3] = 2 − 2 = 0, a[4] = 2 − 2 = 0, a[5] = 1 − 1 = 0. Сумма — 2, как в эталоне.

Полезно проверить, что было бы при s[2] = 1 (нижний край): тогда a[2] = 0, зато a[3] = 2 − 1 = 1. Сумма та же самая — ровно то, что предсказывает нулевой коэффициент при одном потомке.

А вот пример 3 показывает, откуда берётся −1. Там цепочка 1 → 2 → 3, s[1] = 2, s[3] = 1, вершина 2 стёрта. Она обязана быть не меньше 2 (предок) и не больше 1 (потомок) — отрезок пуст. Формально это ловится так: берём потолок от потомка, s[2] = 1, и получаем a[2] = 1 − 2 = −1 < 0. Значит восстановить нельзя.

Идея решения

Алгоритм в одну фразу: каждой стёртой вершине присвоить минимум значений её потомков (а если потомков нет — значение предка), после чего посчитать все разности «вершина минус предок»; если хоть одна отрицательна, ответа нет, иначе ответ — их сумма плюс s[1].

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

Почему берём именно минимум по потомкам. Ограничения на стёртую вершину v: s[v] \ge s[p(v)] (иначе её собственное значение отрицательно) и s[v] \le s[c] для каждого потомка c (иначе отрицательным станет значение потомка). Верхняя граница отрезка — минимум по потомкам, нижняя — значение предка.

Дальше работает подсчёт коэффициента из теории. Значение s[v] входит в итоговую сумму со знаком плюс один раз (в a[v]) и со знаком минус m раз — по разу в каждом a[c]. Общий коэффициент равен $1 - m$, где m — число потомков:

• потомков нет — коэффициент $+1$, значение выгодно опустить до нижней границы: s[v] = s[p(v)], вклад нулевой;
• потомок один — коэффициент 0, ответ не зависит от выбора, можно смело брать верхнюю границу;
• потомков двое и больше — коэффициент отрицательный, значение выгодно поднять до верхней границы, то есть до минимума по потомкам.

Отсюда единое правило: если потомки есть — берём минимум по ним, если нет — значение предка. Разбирать случаи «один потомок» и «много потомков» отдельно не нужно.

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

Приятная деталь входных данных. По условию p[i] < i, то есть предок всегда имеет меньший номер. Значит вершины уже перечислены в порядке «сверху вниз», и обход дерева не нужен вовсе: глубины, минимумы по потомкам и разности считаются простыми проходами по массиву. Это редкость — обычно ради такого порядка приходится запускать поиск в глубину.

Псевдокод

прочитать n, массив предков p[2..n], массив s[1..n]

// глубины: предок всегда имеет меньший номер, поэтому хватает прямого прохода
h[1] = 1
для v от 2 до n:
    h[v] = h[p[v]] + 1

// минимум известных значений среди потомков
min_child[1..n] = +бесконечность
для v от 2 до n:
    если s[v] != -1:
        min_child[p[v]] = min(min_child[p[v]], s[v])

итог = s[1]
для v от 2 до n:
    если h[v] чётная:                       // значение стёрто — выбираем сами
        если min_child[v] == +бесконечность:
            s[v] = s[p[v]]                  // потомков нет: опускаем до предка
        иначе:
            s[v] = min_child[v]              // поднимаем до потолка от потомков
    a = s[v] - s[p[v]]
    если a < 0:
        вывести -1 и завершить
    итог += a

вывести итог

Код решения

Комментарии по реализации. Суммарный ответ может достигать порядка $10^{14}$ — до $10^5$ вершин, у каждой разность до $10^9$, — поэтому накопитель обязан быть 64-битным, хотя сами s в 32 бита ещё помещаются. Массив best_child заполняется по известным значениям до основного цикла: во время него s стёртых вершин уже перезаписывается, и различить «известное» и «назначенное» стало бы невозможно. Проверка s[v] != -1 в первом проходе эквивалентна проверке чётности глубины, но короче и не требует депта — правда, для ясности глубина всё равно нужна во втором проходе.

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

Пример 1: n = 5, все вершины 2–5 — потомки корня, s = [1, −1, −1, −1, −1].

Глубина вершин 2–5 равна 2 — все стёрты, и ни у одной нет потомков. Значит каждой достаётся значение предка: s[v] = s[1] = 1, все разности нулевые.

Итог: 1 + 0 + 0 + 0 + 0 = 1. Наш вывод: 1 — совпадает с ожидаемым.

Пример 2: разобран выше по шагам.

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

Пример 3: цепочка 1 → 2 → 3, s = [2, −1, 1]. Вершина 2 стёрта, её единственный потомок даёт потолок 1, поэтому s[2] = 1, и разность a[2] = 1 − 2 = −1 отрицательна.

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

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

• n = 2. Единственная стёртая вершина — потомок корня без собственных потомков; ответ равен s[1].
• Стёртая вершина без потомков. Самый частый источник ошибки: если по невнимательности присвоить ей ноль или оставить −1, разность станет отрицательной и решение выдаст −1 на корректном тесте.
• Известное значение меньше, чем у предка. Противоречие в исходных данных, никак не связанное со стёртыми вершинами; проверка разностей ловит и его.
• s[1] = 0. Допустимо: значения неотрицательны, ноль в корне ничему не противоречит.
• Цепочка из $10^5$ вершин. Проверка на то, что решение обходится без рекурсии; здесь это выходит само собой, потому что обхода нет вовсе.
• Все значения равны. Все разности нулевые, ответ равен s[1].

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

1. Присваивать стёртой вершине без потомков ноль. Значение обязано быть не меньше, чем у предка; ноль ломает это в любом дереве с ненулевым корнем.
2. Брать максимум по потомкам вместо минимума. Потолок задаёт самый маленький потомок: превысив его, мы делаем отрицательным его собственное значение.
3. Считать best_child уже после перезаписи s. Тогда в минимум попадут назначенные значения стёртых вершин, и ограничения «поедут».
4. 32-битный накопитель ответа. Сумма доходит до $10^{14}$.
5. Определять стёртость по чётности номера, а не глубины. Номера вершин с глубиной никак не связаны.
6. Проверять неотрицательность только у стёртых вершин. Противоречие может быть заложено и в известных данных — как в третьем примере, где виновата пара «корень и его внук».
7. Строить обход в глубину, не заметив, что p[i] < i. Не ошибка, но лишний код и лишний риск упереться в глубину рекурсии.

Сложность

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

---

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

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

• Codeforces 1466D «13th Labour of Heracles» (~CF 1500) — дано дерево с весами вершин; рёбра надо раскрасить ровно в k цветов, а стоимость раскраски равна сумме по цветам весов вершин, задетых рёбрами этого цвета; для каждого k от 1 до n − 1 нужно вывести максимальную стоимость. Подсказка: посчитайте, сколько раз каждая вершина может быть учтена дополнительно, и отсортируйте эти возможности.
• Codeforces 1665C «Tree Infection» (~CF 1600) — заражение распространяется по дереву двумя способами: само собой от заражённой вершины к соседней в её же группе потомков и принудительно в любую выбранную вершину; нужно минимальное число ходов, чтобы заразить всё. Подсказка: сведите дерево к набору чисел «сколько потомков у каждой вершины» и решайте уже про этот набор — само дерево дальше не понадобится.
• Codeforces 1946C «Tree Cutting» (~CF 1600) — надо удалить ровно k рёбер так, чтобы наименьшая из получившихся частей была как можно больше. Подсказка: зафиксируйте кандидат-ответ и жадно отрезайте поддерево, как только оно набрало нужный размер, — здесь жадность работает поверх бинарного поиска по ответу с сессии 5.
• Codeforces 1693B «Fake Plastic Trees» (~CF 1700) — за одну операцию можно прибавить неубывающие величины вдоль пути от корня к вершине; нужно минимальное число операций, чтобы значение каждой вершины попало в свой отрезок. Ближе всего к сегодняшней второй задаче: снизу вверх каждой вершине назначается крайнее допустимое значение, и вопрос только в том, какой из краёв выгоден.

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

---

Что дальше

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

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