Прекрасний зріз#523

Прекрасний зріз (Розбір)

Що взагалі просять. Видаляємо одну вершину — дерево розпадається на компонент, по одній на кожного сусіда. У кожній компоненті знаходимо «центроїд» і додаємо його красу. Треба максимізувати суму по всіх .

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

Крок 1: центроїди піддерев. Підвісимо дерево за вершину . Для кожної вершини порахуємо — центроїд її піддерева. Робиться це знизу вгору одним прийомом:

візьміть центроїд найважчого сина й підіймайтеся від нього до , доки «верхня» частина перевищує половину.

Це коректно, бо центроїд піддерева ніколи не лежить нижче за центроїд найважчого сина, і завжди — на шляху від нього до . Сумарна кількість кроків підйому телескопується і дає лінійний час на все дерево. Якщо на якомусь кроці розмір парний і «верхня» частина рівно половина — маємо двох кандидатів, і тут вибираємо того, у кого більша.

Крок 2: компонента «все інше». Для вершини компоненти — це піддерева всіх її синів (їхні центроїди вже пораховані) плюс компонента з боку батька, яка залежить від . Її обробляємо перепідвішуванням: обходимо дерево в глибину і, спускаючись із в сина , «перевертаємо» ребро — розмір нової верхньої компоненти стає n - \mathrm{sz}(v), а її центроїд знаходимо тим самим підйомом go_root від попереднього центроїда. Повертаючись назад, відновлюємо збережені значення.

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

Крок 3: відповідь. Для кожної сума — це \sum_{v \sim u} a\bigl[\mathrm{cent}(\text{компонента } v)\bigr]; беремо максимум і разом з ним номер вершини.

Складність — \mathcal{O}(n \log n) через сортування сусідів за розміром (або , якщо шукати два максимуми без сортування). При до 3 \cdot 10^5 рекурсію краще замінити на явний стек, а суму краси накопичувати в -бітному: до 3\cdot10^5 \cdot 10^9.