Backup Cable#13117

Backup Cable (Editorial)

Solution

Initially, the road network is a tree. We need to add one edge between two non-adjacent vertices to minimize the total damage caused by removing each original edge independently.

Consider adding an edge between vertices $u$ and $v$ .

Since the original graph is a tree, there is exactly one simple path between $u$ and $v$ . Adding the new edge creates a cycle consisting of this path and the new edge.

If we remove an original edge belonging to this cycle, the graph remains connected, so the damage is $0$ .

Otherwise, removing an original edge splits the graph into two connected components. If their sizes are $s$ and $n - s$ n-s, the damage equals

min (s, n - s) .

\min(s,n-s).

Notice that this value does not depend on which new edge we add, as long as the removed edge does not belong to the created cycle.

Root the original tree at vertex $1$ and let $s z_{v}$ sz_v denote the size of the subtree of vertex $v$ .

For every edge connecting a vertex $v$ to its parent, assign the weight

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

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

Let $S$ be the sum of weights of all original edges:

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

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

If we add an edge between vertices $u$ and $v$ , all original edges on the path between them become part of the cycle and contribute $0$ to the total damage.

Therefore, the resulting total damage is

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

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

Thus, minimizing the total damage is equivalent to finding a path with the maximum possible sum of edge weights.

This is exactly the problem of finding the weighted diameter of a tree.

Let $D$ denote the maximum sum of edge weights along any simple path. Then the answer is

S - D .

S-D.

Since all edge weights are positive and $n \geq 3$ n\ge 3, a weighted diameter contains at least two edges. Therefore, its endpoints are not adjacent, so adding an edge between them is always allowed.

We can find the weighted diameter using dynamic programming on the tree.

Let $d p_{v}$ dp_v be the maximum sum of edge weights along a path starting at vertex $v$ and going down into its subtree.

For every child $u$ of vertex $v$ , consider

d p_{u} + w_{u} .

dp_u+w_u.

Let $b es t_{1}$ best_1 and $b es t_{2}$ best_2 be the two largest values among these candidates, using $0$ if there are fewer than two children.

Then

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

dp_v=best_1.

The maximum-weight path whose highest vertex is $v$ has weight

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

best_1+best_2.

Therefore, the weighted diameter is

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

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

We calculate subtree sizes, the total weight $S$ , and the weighted diameter $D$ in a single bottom-up traversal of the rooted tree.

Complexity Analysis

Building the rooted tree takes $O (n)$ time. Each edge is processed a constant number of times when calculating subtree sizes and the weighted diameter.

Therefore, the total time complexity is $O (n)$ , and the space complexity is $O (n)$ .

Implementation

#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();
}