Видалення вершин#402

Видалення вершин (Розбір)

Відповідь — це формула, а не пошук порядку злиттів. Виявляється, оптимальна вартість для піддерева виражається явно:

\mathrm{cost}(S) \;=\; \sum_{v \in S} a_v \;-\; \sum_{\substack{(u,v) \text{ --- ребро} \\ u, v \in S}} \min(a_u, a_v) \;-\; \min_{v \in S} a_v .

Перевіримо на найпростішому: два міста зі значеннями і . Формула дає (5+3) - 3 - 3 = 2 = |5-3| — саме вартість єдиного злиття. Ланцюжок 1 - 5 - 2: (1+5+2) - (1 + 2) - 1 = 4, і справді вигідно спочатку злити з (ціна , лишається ), а потім з (ціна ) — разом , тоді як інший порядок дає .

Ідея за формулою така: кожне ребро рано чи пізно «спрацьовує», і вигідно зливати так, щоб у момент злиття у вершині вже лежав мінімум її боку — тоді ребро коштує рівно \max(a_u,a_v) - \min(a_u,a_v) від відповідних значень, а сумарно всі значення, крім найменшого в піддереві, «зникають» рівно по одному разу.

Як швидко рахувати. Занумеруємо вершини часом входу під час обходу в глибину — тоді піддерево — це відрізок. У дерево Фенвіка покладемо в позицію величину

f(v) \;=\; a_v \;-\; \sum_{c \,-\, \text{син } v} \min(a_c, a_v).

Сума по відрізку піддерева дає перші два доданки формули: кожне внутрішнє ребро враховується рівно один раз (у своєму батькові), а ребро до батька — ні, бо той лежить поза відрізком. Третій доданок — мінімум на відрізку — дає звичайне дерево відрізків.

Оновлення. Заміна a_x \leftarrow y зачіпає лише два доданки:

  • f(p_x) — там треба замінити \min(a_x, a_{p_x}) на \min(y, a_{p_x});

  • — там змінюється і саме a_x, і вся сума \sum_c \min(a_c, a_x) по всіх синах.

Друге — єдине неочевидне місце: синів може бути багато, перебирати їх не можна. Але

\sum_{c} \min(a_c, X) \;=\; \underbrace{\sum_{a_c < X} a_c}_{\text{сума менших}} \;+\; X \cdot \underbrace{\#\{c : a_c \ge X\}}_{\text{кількість більших}},

тобто достатньо для кожної вершини тримати значення її синів у структурі, що вміє «сума менших» і «кількість більших». Оскільки всі значення, які колись з'являться, відомі заздалегідь (початкові плюс усі із запитів), їх можна стиснути офлайн і завести для кожної вершини маленьке дерево Фенвіка над її власним списком — сумарний розмір усіх таких дерев \mathcal{O}(n + q).

Отже кожен запит — \mathcal{O}(\log n): оновлення чіпає дві позиції глобального дерева Фенвіка, одну позицію дерева мінімумів і одне маленьке дерево Фенвіка.

Загальна складність — \mathcal{O}\bigl((n + q)\log n\bigr). Суми сягають 2 \cdot 10^5 \cdot 10^9, тож потрібен -бітний тип.