Відповідь — це формула, а не пошук порядку злиттів. Виявляється, оптимальна вартість для піддерева виражається явно:
Перевіримо на найпростішому: два міста зі значеннями і . Формула дає (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) від відповідних значень, а сумарно всі значення, крім найменшого в піддереві, «зникають» рівно по одному разу.
Як швидко рахувати. Занумеруємо вершини часом входу під час обходу в глибину — тоді піддерево — це відрізок. У дерево Фенвіка покладемо в позицію величину
Сума по відрізку піддерева дає перші два доданки формули: кожне внутрішнє ребро враховується рівно один раз (у своєму батькові), а ребро до батька — ні, бо той лежить поза відрізком. Третій доданок — мінімум на відрізку — дає звичайне дерево відрізків.
Оновлення. Заміна 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) по всіх синах.
Друге — єдине неочевидне місце: синів може бути багато, перебирати їх не можна. Але
тобто достатньо для кожної вершини тримати значення її синів у структурі, що вміє «сума менших» і «кількість більших». Оскільки всі значення, які колись з'являться, відомі заздалегідь (початкові плюс усі із запитів), їх можна стиснути офлайн і завести для кожної вершини маленьке дерево Фенвіка над її власним списком — сумарний розмір усіх таких дерев \mathcal{O}(n + q).
Отже кожен запит — \mathcal{O}(\log n): оновлення чіпає дві позиції глобального дерева Фенвіка, одну позицію дерева мінімумів і одне маленьке дерево Фенвіка.
Загальна складність — \mathcal{O}\bigl((n + q)\log n\bigr). Суми сягають 2 \cdot 10^5 \cdot 10^9, тож потрібен -бітний тип.