Запасний кабель#13117

Запасний кабель (Розбір)

Розв'язок

Початкова мережа доріг є деревом. Нам потрібно додати одне ребро між двома несуміжними вершинами так, щоб мінімізувати сумарну шкоду від незалежного видалення кожного початкового ребра.

Розглянемо додавання ребра між вершинами $u$ та $v$ .

Оскільки початковий граф є деревом, між $u$ та $v$ існує рівно один простий шлях. Додавання нового ребра утворює цикл, який складається з цього шляху та нового ребра.

Якщо видалити початкове ребро, яке належить цьому циклу, граф залишиться зв'язним, тому шкода дорівнюватиме $0$ .

В іншому випадку видалення початкового ребра розбиває граф на дві компоненти зв'язності. Якщо їхні розміри дорівнюють $s$ та $n - s$ n-s, шкода становитиме

min (s, n - s) .

\min(s,n-s).

Зауважимо, що ця величина не залежить від того, яке нове ребро ми додамо, якщо видалене ребро не належить утвореному циклу.

Підвісимо початкове дерево за вершину $1$ . Нехай $s z_{v}$ sz_v — розмір піддерева вершини $v$ .

Для кожного ребра, яке з'єднує вершину $v$ з її батьком, визначимо вагу

w_{v} = min (s z_{v}, n - s z_{v}) .

w_v=\min(sz_v,n-sz_v).

Позначимо через $S$ суму ваг усіх початкових ребер:

S = v = 2 \sum n w_{v} .

S=\sum_{v=2}^{n}w_v.

Якщо додати ребро між вершинами $u$ та $v$ , усі початкові ребра на шляху між ними належатимуть утвореному циклу та даватимуть внесок $0$ у сумарну шкоду.

Тому сумарна шкода після додавання цього ребра дорівнюватиме

S - e \in p a t h (u, v) \sum w_{e} .

S-\sum_{e\in path(u,v)}w_e.

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

Це задача пошуку зваженого діаметра дерева.

Нехай $D$ — максимальна сума ваг ребер уздовж простого шляху. Тоді відповідь дорівнює

S - D .

S-D.

Оскільки всі ваги ребер додатні та $n \geq 3$ n\ge 3, зважений діаметр містить щонайменше два ребра. Отже, його кінцеві вершини не є суміжними, тому додавання ребра між ними завжди дозволене.

Знайдемо зважений діаметр за допомогою динамічного програмування на дереві.

Нехай $d p_{v}$ dp_v — максимальна сума ваг ребер на шляху, який починається у вершині $v$ та йде вниз у її піддерево.

Для кожного сина $u$ вершини $v$ розглянемо значення

d p_{u} + w_{u} .

dp_u+w_u.

Нехай $b es t_{1}$ best_1 та $b es t_{2}$ best_2 — два найбільші значення серед цих кандидатів. Якщо синів менше ніж два, відсутні значення вважатимемо рівними $0$ .

Тоді

d p_{v} = b es t_{1} .

dp_v=best_1.

Максимальна вага шляху, найвищою вершиною якого є $v$ , дорівнює

b es t_{1} + b es t_{2} .

best_1+best_2.

Отже, зважений діаметр дерева можна знайти за формулою

D = v = 1 max n (b es t_{1} + b es t_{2}) .

D=\max_{v=1}^{n}(best_1+best_2).

Розміри піддерев, суму ваг $S$ та зважений діаметр $D$ обчислимо за один обхід підвішеного дерева знизу вгору.

Асимптотична складність

Побудова підвішеного дерева займає $O (n)$ часу. Кожне ребро обробляється сталу кількість разів під час обчислення розмірів піддерев та зваженого діаметра.

Отже, загальна часова складність становить $O (n)$ , а просторова — $O (n)$ .

Реалізація

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;

    vector<vector<int>> g(n + 1);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> par(n + 1), order;
    order.push_back(1);

    for (int i = 0; i < (int)order.size(); i++) {
        int v = order[i];

        for (int u : g[v]) {
            if (u == par[v]) continue;

            par[u] = v;
            order.push_back(u);
        }
    }

    vector<int> sz(n + 1, 1);
    vector<ll> dp(n + 1);

    ll sum = 0, diam = 0;

    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];

        ll best1 = 0, best2 = 0;

        for (int u : g[v]) {
            if (par[u] != v) continue;

            sz[v] += sz[u];

            ll w = min(sz[u], n - sz[u]);
            sum += w;

            ll cur = dp[u] + w;

            if (cur > best1) {
                best2 = best1;
                best1 = cur;
            } else if (cur > best2) {
                best2 = cur;
            }
        }

        dp[v] = best1;
        diam = max(diam, best1 + best2);
    }

    cout << sum - diam << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
}