Козак Вус та ще одна задача#39

Козак Вус та ще одна задача (Editorial)

Що насправді робить операція. Застосування до забирає поточне значення a_i у відповідь і зменшує на нього наступника a_{b_i}. Отже операція над псує лише одну комірку — b_i. Звідси правило:

якщо опрацювати раніше за всіх своїх попередників (тих , для яких b_j = i), то a_i потрапить у відповідь неушкодженим.

Побудуємо функціональний граф: з кожної вершини виходить рівно одне ребро в b_i (або жодного, якщо b_i = -1). Такий граф — це набір циклів, до яких «підвішені» дерева, спрямовані до циклів.

Дерева безкоштовні. У деревній частині потрібний порядок завжди існує: спочатку вершини, ближчі до циклу, потім — дальші. Тому кожне додатне a_i з дерев можна забрати повністю, а від'ємні просто пропустити. Це дає базову оцінку

\sum_{i} \max(a_i, 0).

Цикл — єдине місце, де щось втрачається. Нехай цикл v_1 \to v_2 \to \ldots \to v_k \to v_1. Умова «кожен раніше за свого попередника» означає, що v_{i+1} має йти раніше за v_i — і так по колу, аж поки не отримаємо, що v_1 раніше за v_1. Суперечність. Отже рівно в одному місці циклу правило доведеться порушити.

Порахуємо ціну порушення. Якщо v_{i-1} опрацювати першим і він забере , то в v_i залишиться a_{v_i} - x, і разом вони дадуть x + (a_{v_i} - x) = a_{v_i} — тобто внесок просто зникає. Те саме дає й альтернатива: взагалі пропустити одну вершину. Отже цикл коштує рівно одне зі своїх значень, і ми, звісно, обираємо найменше.

Але якщо на циклі є значення , то рвати цикл треба саме там — пропустити недодатну вершину нам і так вигідно, тож цикл обходиться безкоштовно.

Петля — особливий випадок. При b_i = i операція спершу додає a_i до відповіді, потім віднімає a_i від самого a_i — але значення вже зараховане, а комірка все одно обнуляється. Жодної суперечності « раніше за » немає, тож петля нічого не коштує. Це найлегше місце помилитися.

Разом:

\text{відповідь} \;=\; \sum_i \max(a_i, 0) \;-\; \sum_{\substack{\text{цикли довжини } \ge 2 \\ \text{з усіма } a > 0}} \ \min_{v \in \text{цикл}} a_v .

Реалізація. Шукаємо цикли звичайним проходом по функціональному графу: йдемо за посиланнями, позначаючи вершини «на поточному шляху»; щойно натрапили на вершину зі своїм же поточним позначенням — знайшли цикл, а його початок дає позиція, яку зберегли для цієї вершини. Наприкінці всі вершини шляху позначаємо як завершені. Це без рекурсії. Сума сягає 10^5 \cdot 10^9, тож біти обов'язкові.