Anton the Guard (Editorial)

Формалізація. Пріоритет — це глибина в ребрах, якщо підвісити дерево за об'єкт $1$. Антон іде маршрутом, який спершу покриває весь рівень $1$, потім весь рівень $2$ і так далі. Зауважте, що проходити «транзитом» через ще не відвідані об'єкти неможливо: шлях між двома вершинами рівня $d$ піднімається до їхнього найближчого спільного предка й спускається назад, а це лише вершини глибини $<d$ — усі вже відвідані. Тож обмеження порядку нічого не ламає, і задача суто оптимізаційна.

Ціна одного рівня. Класична лема: якщо треба, стартувавши з $u$, обійти всі вершини множини $S$ і закінчити в $v$, то мінімальна довжина маршруту дорівнює

де $W$ — сумарна вага мінімального піддерева, що містить усі ці вершини. Пояснення просте: обхід дерева проходить кожним ребром двічі, окрім ребер шляху u \to v, якими достатньо пройти по одному разу.

Динаміка по рівнях. Нехай S_d — вершини глибини $d$, а \mathrm{dp}_d[v] — мінімальна довжина маршруту, що вже обійшов усі рівні до $d$ включно й завершився у вершині v \in S_d. Тоді

(вершина $v$ уже належить S_{d+1}, тож окремо її додавати не треба). Відповідь — мінімум $\mathrm{dp}$ на останньому рівні.

Чому це рахується швидко. Батько кожної вершини з S_{d+1} лежить у S_d. Тому стягуюче дерево T_{d+1} множини S_{d+1} — це «ребра до батьків» плюс стягуюче дерево самих батьків, яке живе на рівні $d$ і вище. Для u \in S_d додавання $u$ коштує рівно \mathrm{dist}(u, T_{d+1}), а якщо позначити e_u — точку, якою шлях від $u$ входить у T_{d+1}, то

Отже

і всі величини живуть усередині стягуючого дерева рівня.

Реалізація. Для кожного рівня будуємо віртуальне дерево: сортуємо вершини рівня за часом входу обходу в глибину, додаємо попарні $\mathrm{LCA}$ сусідніх, стискаємо. Сумарний розмір усіх віртуальних дерев — $\mathcal{O}(n)$, бо кожна вершина належить рівно одному рівню. Далі по віртуальному дереву робимо звичні два обходи (знизу вгору, потім згори вниз), проштовхуючи найкраще значення \mathrm{dp}_d[u] + \mathrm{dist}(u, \cdot) до кожної вершини. Класична пастка: у вершині треба тримати два найкращі значення з різних піддерев — інакше при спуску назад у ту саму гілку значення «використає саме себе».

$\mathrm{LCA}$ і відстані зручно брати важко-легкою декомпозицією або двійковими підйомами.

Складність — \mathcal{O}(n \log n). При $n$ до 10^6 потрібне швидке зчитування, ітеративні обходи замість рекурсії (глибина може сягати 10^6) та $64$-бітні суми: відповідь сягає 2 \cdot 10^6 \cdot 10^9.