题解 P9701【[GDCPC2023] Classic Problem】

题如其名，确实挺经典的。

我们称边权在输入中给定的边为特殊边，其它边为平凡边。称特殊边涉及到的点为特殊点，其它点为平凡点。

显然，对于连续的若干平凡点 \([l,r]\)，他们内部的最优连边方式就是连成一条链，花费 \(r-l\) 的代价。我们先把这样的代价加到答案中，然后将极长连续平凡点缩成一个点，称为区间点。

我们可以按照编号从小到大的顺序为区间点和特殊点重新标号。问题转化为给定一个由区间点和特殊点构成的 \(O(m)\) 点的完全图，求它的最小生成树。

有特殊性质的点数特别多的稠密图的最小生成树问题一般考虑使用 Boruvka 算法进行求解。对于图 \(G=(V,E)\) 求最小生成树，Boruvka 算法的思路是：每一轮找到每个连通块向外连的边权最小的边，在这轮结束后把所有最小边连上，直到整个图连通为止。显然，每一轮过后连通块数至少减半，因此轮数为 \(O(\log|V|)\)，复杂度为 \(O(|E|\log|V|)\)。我们可以利用图的特殊性质，加速找到最小边的过程，使得复杂度降至 \(O(|V|\log|V|)\)。

在每一轮开始时，预处理 \(pre(u),suc(u)\) 表示节点 \(u\) 前面/后面最近的不在同一连通块的点。对于区间点，它的最小边一定是它与 \(pre(u)\) 或 \(suc(u)\) 之间的。对于特殊点，首先判一遍所有跨连通块的特殊边，然后分别找到前面/后面最近的既不在同一连通块又没有特殊边相连的点，看看哪个更小即可。可以证明，每轮的时间复杂度为 \(O(|V|)\)，总复杂度为 \(O(|V|\log|V|)\)。由于重建的图的点数 \(|V|=O(m)\)，总复杂度为 \(O(m\log m)\)。

// Problem: T368344 [GDCPC2023] L-Classic Problem
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/T368344?contestId=135929
// Memory Limit: 1 MB
// Time Limit: 8000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(ll x = (y); x <= (z); ++x)
#define per(x, y, z) for(ll x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
ll randint(ll L, ll R) {
    uniform_int_distribution<ll> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const ll N = 5e5 + 5, inf = 0x1f1f1f1f1f1f1f1fll;

ll T, n, m, U[N], V[N], W[N], buc[N], tot, cntV, val[N], pos[N], pre[N], suc[N], vis[N];
map<ll, ll> id;

struct Vertex {
    ll l, r;
    bool special;
    vector<tuple<ll, ll>> e;
}vtx[N];

struct Dsu {
    ll fa[N];
    void init(ll x) {rep(i, 1, x) fa[i] = i;}
    bool isroot(ll x) {return x == fa[x];}
    ll find(ll x) {return isroot(x) ? x : fa[x] = find(fa[x]);}
    bool same(ll x, ll y) {return find(x) == find(y);}
    bool merge(ll x, ll y) {
        if(same(x, y)) return false;
        x = find(x); y = find(y);
        fa[x] = y;
        return true;
    }
}dsu;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    for(cin >> T; T; --T) {
        cin >> n >> m;
        rep(i, 1, m) {
            cin >> U[i] >> V[i] >> W[i];
            buc[++tot] = U[i];
            buc[++tot] = V[i];
        }
        sort(buc + 1, buc + 1 + tot);
        tot = unique(buc + 1, buc + 1 + tot) - buc - 1;
        ll lst = 0;
        rep(i, 1, tot) {
            // segment
            if(buc[i] - lst + 1 >= 3) {
                ++cntV;
                vtx[cntV].l = lst + 1;
                vtx[cntV].r = buc[i] - 1;
                vtx[cntV].special = false;
            }
            // special
            ++cntV;
            vtx[cntV].l = vtx[cntV].r = buc[i];
            vtx[cntV].special = true;
            id[buc[i]] = cntV;
            lst = buc[i];
        }
        // segment
        if(n - lst + 1 >= 2) {
            ++cntV;
            vtx[cntV].l = lst + 1;
            vtx[cntV].r = n;
            vtx[cntV].special = false;
        }
        rep(i, 1, m) {
            vtx[id[U[i]]].e.emplace_back(id[V[i]], W[i]);
            vtx[id[V[i]]].e.emplace_back(id[U[i]], W[i]);
        }
        ll edges = 0, ans = 0;
        rep(u, 1, cntV) ans += vtx[u].r - vtx[u].l;
        dsu.init(cntV);
        while(edges < cntV - 1) { // MST - Boruvka algorithm
            rep(u, 1, cntV) {
                if(dsu.isroot(u)) {
                    val[u] = inf;
                    pos[u] = -1;
                }
            }
            rep(u, 1, cntV) {
                if(vtx[u].special) {
                    for(auto [v, w] : vtx[u].e) {
                        if(!dsu.same(u, v) && w < val[dsu.find(u)]) {
                            val[dsu.find(u)] = w;
                            pos[dsu.find(u)] = dsu.find(v);
                        }
                    }
                }
            }
            pre[1] = 0;
            rep(i, 2, cntV) pre[i] = dsu.same(i - 1, i) ? pre[i - 1] : i - 1;
            suc[cntV] = cntV + 1;
            per(i, cntV - 1, 1) suc[i] = dsu.same(i, i + 1) ? suc[i + 1] : i + 1;
            rep(u, 1, cntV) {
                if(vtx[u].special) for(auto [v, w] : vtx[u].e) vis[v] = 1;
                for(ll v = u; v >= 1; ) {
                    if(dsu.same(v, u)) v = pre[v];
                    else if(vis[v]) --v;
                    else {
                        if(vtx[u].l - vtx[v].r < val[dsu.find(u)]) {
                            val[dsu.find(u)] = vtx[u].l - vtx[v].r;
                            pos[dsu.find(u)] = dsu.find(v);
                        }
                        break;
                    }
                }
                for(ll v = u; v <= cntV; ) {
                    if(dsu.same(u, v)) v = suc[v];
                    else if(vis[v]) ++v;
                    else {
                        if(vtx[v].l - vtx[u].r < val[dsu.find(u)]) {
                            val[dsu.find(u)] = vtx[v].l - vtx[u].r;
                            pos[dsu.find(u)] = dsu.find(v);
                        }
                        break;
                    }
                }
                if(vtx[u].special) for(auto [v, w] : vtx[u].e) vis[v] = 0;
            }
            rep(u, 1, cntV) {
                if(dsu.isroot(u) && pos[u] != -1 && dsu.isroot(pos[u])) {
                    ++edges;
                    ans += val[dsu.find(u)];
                    dsu.merge(u, pos[u]);
                }
            }
        }
        cout << ans << endl;
        rep(i, 1, tot) buc[i] = id[i] = 0;
        rep(i, 1, cntV) {
            vis[i] = vtx[i].l = vtx[i].r = 0;
            vtx[i].special = false;
            vtx[i].e.clear();
        }
        tot = cntV = 0;
    }
    return 0;
}