CERC2014 Pork barrel

· · 题解

考虑 Kruskal 算法的过程，即边权从小到大依次加入边，每条边连接两个连通块。很重要的性质是每次加入的边边权单调不降。

于是权值 [L,R] 内的边组成的最小生成树，相当于从权值为 L 的边开始跑 Kruskal，取所有 \ge L 的边组成的最小生成树，树上所有边权 \le R 的边的边权之和。

将边从小到大排序，如果对于每个边权 L，求出边权 \ge L 的一段后缀的边组成的最小生成树，就能够通过一些可持久化手段维护出此时边权 \le R 的边的边权之和。

若已经求出 L'\ge L 的最小生成树（L' 是 L 值域上的后继）T'，考虑新增 (u,v,L) 这条边，得到新的最小生成树 T：

注意到 n\le 10^3，这允许我们在 O(nm) 的时间内求出这 m 棵最小生成树。

由于 T'\to T 的边权变化是 O(1) 的，于是只需要一个支持单点修改，区间求和的可持久化数据结构。使用可持久化权值线段树即可。

复杂度 O(nm+(m+q)\log W)。

// Problem: P4764 [CERC2014] Pork barrel
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4764
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

namespace vbzIO {
    char ibuf[(1 << 20) + 1], *iS, *iT;
    #if ONLINE_JUDGE
    #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
    #else
    #define gh() getchar()
    #endif
    #define mt make_tuple
    #define mp make_pair
    #define fi first
    #define se second
    #define pc putchar
    #define pb emplace_back
    #define ins insert
    #define era erase
    typedef tuple<int, int, int> tu3;
    typedef pair<int, int> pi;
    inline int rd() {
        char ch = gh();
        int x = 0;
        bool t = 0;
        while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
        return t ? ~(x - 1) : x;
    }
    inline void wr(ll x) {
        if (x < 0) x = ~(x - 1), putchar('-');
        if (x > 9) wr(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace vbzIO;

const int N = 1e3 + 100;
const int M = 1e5 + 100;
const int W = 1e6;

struct edge {
    int u, v, w;
    edge () { }
    edge (int _u, int _v, int _w) : u(_u), v(_v), w(_w) { }
    bool operator < (const edge &rhs) const { return w < rhs.w; }
} e[M], st[N];
int n, m, q, fl, tar, tot, tp, rt[M];
set<pi> t[N];

struct seg { ll s; int lc, rc; } tr[M << 6];

#define ls tr[x].lc
#define rs tr[x].rc
#define mid ((l + r) >> 1)

void upd(int l, int r, int p, int op, int lt, int &x) {
    tr[x = ++tot] = tr[lt], tr[x].s += op * p;
    if (l == r) return;
    if (p <= mid) upd(l, mid, p, op, tr[lt].lc, ls);
    else upd(mid + 1, r, p, op, tr[lt].rc, rs);
}

int qry(int l, int r, int s, int t, int x) {
    if (!x) return 0;
    if (s <= l && r <= t) return tr[x].s;
    int res = 0;
    if (s <= mid) res += qry(l, mid, s, t, ls);
    if (t > mid) res += qry(mid + 1, r, s, t, rs);
    return res;
}

void dfs(int u, int fa) {
    if (u == tar) return fl = 1, void();
    for (pi p : t[u]) {
        int v = p.fi, w = p.se;
        if (v == fa) continue;
        st[++tp] = edge(u, v, w), dfs(v, u);
        if (fl) return;
        tp--;
    }
}

void init() {
    for (int i = 1; i <= m; i++) rt[i] = 0;
    for (int i = 1; i <= n; i++) t[i].clear();
    tot = 0;
}

void solve() {
    n = rd(), m = rd();
    for (int i = 1, u, v, w; i <= m; i++) 
        u = rd(), v = rd(), w = rd(), e[i] = edge(u, v, w);
    sort(e + 1, e + m + 1);
    for (int i = m; i; i--) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        fl = tp = 0, tar = v, dfs(u, 0), rt[i] = rt[i + 1];
        if (fl) {
            edge res = edge(0, 0, 0);
            for (int i = 1; i <= tp; i++)
                res = max(res, st[i]);
            t[res.u].era(mp(res.v, res.w)), t[res.v].era(mp(res.u, res.w));
            upd(1, W, res.w, -1, rt[i], rt[i]);
        }
        t[u].ins(mp(v, w)), t[v].ins(mp(u, w));
        upd(1, W, w, 1, rt[i], rt[i]);
    }
    q = rd();
    int lst = 0;
    while (q--) {
        int l = rd() - lst, r = rd() - lst;
        int p = lower_bound(e + 1, e + m + 1, edge(0, 0, l)) - e;
        if (p > m) { lst = 0, puts("0"); continue; }
        wr(lst = qry(1, W, l, r, rt[p])), pc('\n');
    }
    init();
}

int main() {
    int T = rd();
    while (T--) solve();
    return 0;
}