p529.cpp
======================
#include <bits/stdc++.h>
#define endl '\n'

// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

using namespace std;
template<class T, class T2>
inline int chkmax(T& x, const T2& y) {
    return x < y ? x = y, 1 : 0;
}
template<class T, class T2>
inline int chkmin(T& x, const T2& y) {
    return x > y ? x = y, 1 : 0;
}
const int MAXN = (1 << 20);
const int B = 200;

struct dsu {
    int n;
    vector<int> par, sz;
    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 1);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
        }
    }
    int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
    bool connected(int u, int v) { return root(u) == root(v); }
    void unite(int u, int v) {
        u = root(u);
        v = root(v);
        if(u == v) {
            return;
        }
        if(sz[u] < sz[v]) {
            swap(u, v);
        }
        par[v] = u;
        sz[u] += sz[v];
    }
};

struct edge {
    int u, v, w, i;
    edge() { u = v = w = i = 0; }
    edge(int _u, int _v, int _w, int _i) {
        u = _u;
        v = _v;
        w = _w;
        i = _i;
    }
};

bool cmp(const edge& x, const edge& y) { return x.w < y.w; }

int n, m;
edge ed[MAXN], nw_li[MAXN], important[MAXN];
pair<int, int> que[MAXN];

void read() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
        ed[i].i = i;
    }
}

int64_t answer[MAXN];
int pos_edge[MAXN], imp_sz;
bool used[MAXN], used2[MAXN];
int comp_id[MAXN];
dsu additional_d, tmp, d;

int get(int x) { return comp_id[additional_d.root(x)]; }

void solve() {
    sort(ed, ed + m, cmp);
    for(int i = 0; i < m; i++) {
        pos_edge[ed[i].i] = i;
    }

    int q;
    cin >> q;

    for(int i = 0; i < q; i++) {
        cin >> que[i].first >> que[i].second;
        que[i].first--;
    }

    for(int st = 0; st < q; st += B) {
        int en = min(q - 1, st + B - 1);
        for(int i = 0; i < m; i++) {
            used[i] = used2[i] = 0;
        }
        for(int i = st; i <= en; i++) {
            used[que[i].first] = 1;
        }

        tmp.init(n);
        additional_d.init(n);
        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                tmp.unite(ed[i].u, ed[i].v);
            }
        }

        int64_t sum = 0;
        for(int i = 0; i < m; i++) {
            if(!used[ed[i].i] && !tmp.connected(ed[i].u, ed[i].v)) {
                sum += ed[i].w;
                tmp.unite(ed[i].u, ed[i].v);
                additional_d.unite(ed[i].u, ed[i].v);
            }
        }

        int cnt = 0;
        for(int i = st; i <= en; i++) {
            answer[i] = sum;
        }
        for(int i = 1; i <= n; i++) {
            if(i == additional_d.root(i)) {
                comp_id[i] = cnt++;
            }
        }

        d.init(cnt);
        imp_sz = 0;
        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                continue;
            }

            int u = get(ed[i].u), v = get(ed[i].v);
            if(!d.connected(u, v)) {
                d.unite(u, v);
                important[imp_sz++] = ed[i];
            }
        }

        for(int i = 0; i < imp_sz; i++) {
            used2[important[i].i] = 1;
        }

        for(int i = 0; i < m; i++) {
            if(used[ed[i].i]) {
                important[imp_sz++] = ed[i];
            }
        }

        sort(important, important + imp_sz, cmp);

        for(int i = st; i <= en; i++) {
            int w = que[i].second, idx = que[i].first;

            for(int ii = 0; ii < imp_sz; ii++) {
                if(important[ii].i == idx) {
                    important[ii].w = w;
                }
            }

            for(int ii = 1; ii < imp_sz; ii++) {
                if(cmp(important[ii], important[ii - 1])) {
                    swap(important[ii], important[ii - 1]);
                }
            }
            for(int ii = imp_sz - 2; ii >= 0; ii--) {
                if(cmp(important[ii + 1], important[ii])) {
                    swap(important[ii], important[ii + 1]);
                }
            }

            d.init(cnt);
            for(int ii = 0; ii < imp_sz; ii++) {
                int u = get(important[ii].u), v = get(important[ii].v),
                    w = important[ii].w;
                if(!d.connected(u, v)) {
                    answer[i] += w, d.unite(u, v);
                }
            }
        }

        int p = 0, I = 0, J = 0;
        while(I < m && J < imp_sz) {
            if(used[ed[I].i]) {
                I++;
                continue;
            }
            if(used2[important[J].i]) {
                J++;
                continue;
            }

            if(cmp(ed[I], important[J])) {
                nw_li[p++] = ed[I++];
            } else {
                nw_li[p++] = important[J++];
            }
        }

        while(I < m) {
            if(used[ed[I].i]) {
                I++;
                continue;
            }
            nw_li[p++] = ed[I++];
        }

        while(J < imp_sz) {
            if(used2[important[J].i]) {
                J++;
                continue;
            }
            nw_li[p++] = important[J++];
        }

        for(int i = 0; i < m; i++) {
            ed[i] = nw_li[i];
        }
        for(int i = 0; i < m; i++) {
            pos_edge[ed[i].i] = i;
        }
    }

    for(int i = 0; i < q; i++) {
        cout << answer[i] << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    read();
    solve();
    return 0;
}

=================
statement.txt
======================
529. It's Time to Repair the Roads
Time limit per test: 2.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Everybody knows about the problems with roads in Berland. The government has been trying to undertake major repairs for many years, but the roads have never been repaired due to the lack of money in the budget.

There are n cities and m roads in Berland. The cities are numbered from 1 to n. The roads are numbered from 1 to m. Each road connects a pair of different cities, all the roads are two-way. There is at most one road between any pair of cities. The cost of repairing is known for each road.

Clearly, repairing all roads in Berland is an unaffordable luxury, so the government decided to repair only such set of the roads, that it's possible to get from any city to any other city by the roads from this repaired set, and the total cost of these road works is minimal.

In the circumstances of the global economic crisis and global warming, road repair costs change every day. Berland's scientists managed to predict these changes, concluding that the cost of road works will change for only one road each day. They created a full list of expected changes for the coming t days — for each day they came up a road and its new repair cost.

The government of Berland would like to know when it would be better to repair the roads, so they need to figure out the cost of road works for every of the coming t days before making a final decision. Your task is to help them and figure out the total repair cost of Berland's road system at the end of each these t days. As repair costs change over time, the set of selected roads can change on a daily basis as well.

Input
The first line contains a pair of integers n,m (2 ≤ n ≤ 40000, n - 1 ≤ m ≤ 40000), where n — the amount of cities, m — the amount of roads. Each of the following m lines contains a road description: three integer numbers xi, yi and pi (1 ≤ xi, yi ≤ n, xi ≠ yi, 1 ≤ pi ≤ 40000), where xi and yi are indices of the cities connected by the given road, and pi — initial cost of repairing it.

Then there follows a line with the only number t (1 ≤ t ≤ 40000), t — amount of days. The following t lines contain the scientists' predictions for the coming t days. Each of t lines contains a pair of integer numbers ei, ci (1 ≤ ei ≤ m, 1 ≤ ci ≤ 40000), where ci — is the new repair cost for the road ei.

It's possible to get from any city to any other city by the roads. The cost of repair for a single road can be changed more than once over time.

Output
Output t lines, each of them should contain the road system's total repair cost at the end of each day.

Example(s)
sample input
sample output
4 6
1 2 10
2 3 20
2 4 30
1 3 40
3 4 50
4 1 60
3
4 22
5 17
4 14
60
47
41

sample input
sample output
3 3
3 2 4
3 1 4
2 1 3
3
2 5
2 2
2 5
7
5
7

=================
