Lời giải

Đầu tiên chúng ta sẽ xây một cây khung nhỏ nhất của đồ thị với cho.

• Với mọi cạnh có trong cây khung nhỏ nhất này, thì đáp án của cạnh đó là tổng trọng số của cây khung.
• Với các cạnh còn lại, gọi cạnh đang xét là cạnh ~(x, y)~. Chúng ta sẽ thêm cạnh ~(x, y)~ vào cây khung nhỏ nhất, tạm thời tạo một chu trình. Sau đó ta bỏ đi cạnh khác ~(x, y)~ có trọng số lớn nhất trong chu trình này để tạo thành một cây khung. Cây khung này sẽ là cây khung nhỏ nhất mà bao gồm cạnh ~(x, y)~.

Điều này có thể được chứng minh bằng tính chất Đường đi hẹp nhất có trong blog trên.

Việc bỏ đi cạnh khác ~(x, y)~ có trọng số lớn nhất trong chu trình này để tạo thành một cây khung, nói cách khác, chính là tìm cạnh có trọng số lớn nhất trên đường đi ngắn nhất từ ~x~ đến ~y~ trên cây khung nhỏ nhất.

Gọi ~lca(a, b)~ là đỉnh xa gốc nhất mà là tổ tiên của ~a~ và ~b~.
Gọi ~d(u)~ là số cạnh trong đường đi từ gốc tới đỉnh ~u~.

Dễ thấy cạnh có trọng số lớn nhất trên đường đi ngắn nhất từ ~x~ đến ~y~ bằng giá trị bé hơn trong cạnh có trọng số lớn nhất trên đường đi ngắn nhất từ ~x~ đến ~lca(x, y)~ và ~y~ đến ~lca(x, y)~. Vậy ta phải tìm ~lca(x, y)~ và hai giá trị kia một cách hiệu quả. Ta có thể sử dụng kĩ thuật bước nhảy nhị phân (binary lifting) để giải cả hai bài toán này. Kĩ thuật được miêu tả sau đây:

Đầu tiên, ta dựng hai mảng hai chiều ~up~ với ~up[i][j]~ là tổ tiên thứ ~2^j~ của đỉnh ~i~ và mảng ~val~ với ~val[i][j]~ là giá trị của cạnh lớn nhất trong đường đi từ đỉnh ~i~ đến tổ tiên thứ ~2^j~ của đỉnh ~i~. Để xây được hai mảng này ta nhận thấy rằng ~up[i][j] = up[up[i][j - 1]][j - 1]~ và ~val[i][j] = max(val[i][j - 1], val[up[i][j - 1]][j - 1])~ nên dfs một lần qua cây là có thể dựng được. Độ phức tạp: ~\mathcal{O}(n\log{}n)~.
Để xác định ~lca(a, b)~ ta thực hiện các bước sau:

• Giả sử ~d(a) > d(b)~, ta thay a bằng tổ tiên thứ ~d(a) - d(b)~ của a. Khi này, ~d(a) = d(b)~.
• Ta thay ~a~ và ~b~ bằng hai đỉnh tổ tiên tương ứng sao cho ~d(a) = d(b)~ cho đến khi ~a = b~. Ta sẽ sử dụng mảng ~up~ để làm điều này một cách hiệu quả. Đỉnh ~a~ khi này sẽ là kết quả của bài toán.
• Để tìm cạnh có trọng số lớn nhất trên đường đi, ta lấy max các giá trị của mảng ~val~ y như cách sử dụng mảng ~up~.
  Độ phức tạp: ~\mathcal{O}(\log{}n)~.

Tổng độ phức tạp bài toán: ~\mathcal{O}(m\log{m} + n\log{n} + m\log{n})~.

Code mẫu

#include <bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

struct Edge{
    int u, v, w, id;
    bool operator< (Edge const& other) const{
        return w < other.w;
    }
};

const int N = 2e5 + 5;
int n, m, sum;
int par[N], sz[N], res[N], up[N][18], val[N][18], d[N];
vector<Edge> edges;
vector<pii> g[N];

int find_set(int v) {
    return (v == par[v] ? v : par[v] = find_set(par[v]));
}

bool join_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a == b) return 0;

    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
    return 1;
}

void dfs(int u, int p) {
    for (int i = 1; i <= 17; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
        val[u][i] = max(val[u][i - 1], val[up[u][i - 1]][i - 1]);
    }

    for (auto e : g[u]) {
        int v = e.first, w = e.second;
        if (v == p) continue;
        up[v][0] = u;
        val[v][0] = w;
        d[v] = d[u] + 1;
        dfs(v, u);
    }
}

int get(int u, int v) {
    int res = 0;
    if (d[u] < d[v]) swap(u, v);
    for (int i = 17; i >= 0; i--) if (d[u] - d[v] >= (1 << i)) {
        res = max(res, val[u][i]);
        u = up[u][i];
    }
    if (u == v) return res;

    for (int i = 17; i >= 0; i--) if (up[u][i] != up[v][i]) {
        res = max({res, val[u][i], val[v][i]});
        u = up[u][i];
        v = up[v][i];
    }
    return max({res, val[u][0], val[v][0]});
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        par[i] = i;
        sz[i] = 1;
    }
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        edges.push_back({u, v, w, i});
    }

    sort(edges.begin(), edges.end());
    for (auto e : edges) if (join_sets(e.u, e.v)) {
        g[e.u].push_back({e.v, e.w});
        g[e.v].push_back({e.u, e.w});
        sum += e.w;
    }

    dfs(1, 0);
    for (auto e : edges) res[e.id] = sum - get(e.u, e.v) + e.w;

    for (int i = 1; i <= m; i++) cout << res[i] << "\n";

}