最小生成树 / MST

· · 算法·理论

LCT 求法

对连通无向图 G=(V,E),设其 MST 为 T。考虑如下过程:

使用 LCT 维护 T。可以证明,上述算法总能得到 MST。

Kruskal

对 E 按边权升序排序,顺次枚举 e \in E。

若 e 加入后成环,根据枚举顺序 e 一定是环上的最大边,直接删去即可。使用并查集维护 T。

对于 n,m 同阶的稀疏图,一般使用 Kruskal 求 MST。

Prim

选取任意顶点 u \in V,逐步扩展 T。每步在所有连接树内顶点和树外顶点的边中,选择权值最小边 e 加入 T。

由于 e 必有一端在树外,所以加入 e 后不会成环。

Boruvka

初始将 n 个顶点视作 n 个连通块。

每轮操作中,同时考虑当前所有连通块,找出从块内出发连向其他块的最小边。将所有最小边同时加入 T 并合并连通块。

若边权互不相同,则合并过程不会成环,且每轮连通块数目折半,只会执行 O(\log n) 轮。如果有相同边权,可以人为钦定第二关键字得到一个严格全序。

下面给出模板题的 Boruvka 写法。

:::::info[代码]

const int N = 2e5 + 5, inf = 1e9;
int n, m, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
using info = pair<int, int>;
vector<pair<int, info>> e[N];
pair<info, int> out[N];

i64 boruvka() {
    iota(fa + 1, fa + n + 1, 1);
    i64 res = 0;
    for (int cnt = 0; cnt < n - 1; ) {
        fill(out + 1, out + n + 1, make_pair(info{inf, -1}, -1));
        for (int u = 1; u <= n; u++) 
            for (auto [v, w] : e[u]) {
                if (find(u) == find(v)) continue;
                if (w < out[find(u)].fi) out[find(u)] = {w, v};
            }
        for (int u = 1; u <= n; u++) {
            if (u != find(u) || out[u].se == -1) continue;
            int fu = u, fv = find(out[u].se);
            if (fu != fv) fa[fu] = fv, cnt++, res += out[u].fi.fi; 
        }
    } return res;
}

void _main() {
    cin >> n >> m;
    iota(fa + 1, fa + n + 1, 1);
    for (int i = 1, u, v, c; i <= m; i++) {
        cin >> u >> v >> c; info w(c, i);
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
        fa[find(u)] = find(v);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (i == find(i)) cnt++;
    if (cnt > 1) return cout << "orz", void();
    cout << boruvka();
}

:::::

Kruskal 重构树

在 Kruskal 过程中,设边 e=(u,v,w) 加入 MST。新建节点 x,点权为 w,将 u,v 所在连通块的代表元作为 x 的左右儿子。合并 u,v 所在连通块时,将 x 作为新连通块的代表元。

可以发现下列性质:

LP 形式

MST 可以写成如下 LP 问题:

\begin{aligned} \min& \sum_{e \in E} x_e w_e\\ \text{subject to } & \sum_{e \in E}x_e=n-1,\\ & \sum_{e \in E(S)} x_e \le |S|-1, \forall S \subseteq V, 2 \le |S| < n,\\ & 0 \le x_e \le 1. \end{aligned}

上面的式子中:

得到 MST 问题具有凸性,可以使用凸优化等方法求解。

练习

P14362 [CSP-S 2025] 道路修复

给定 n 个点 m 条边的无向连通图 G=(V,E),边带权。

现有 k 种决策,第 i 种决策新建顶点 x,对所有 u \in V 连边 u \leftrightarrow x,边权为 a_{i,u}。选择第 i 种决策需要 c_i 的代价。

你可以选择任意决策,代价定义为新图 MST 边权和加上所选决策的总代价。最小化代价并输出。

:::::success[题解]

注意到 k\le 10,考虑枚举每个决策是否选择,对新图使用 Kruskal 求 MST,复杂度 O(2^k m\log m)。

设 G 的 MST 为 T,上述过程中,来自原图的边可以只保留 T 中的边,从而 O(m) 的边数降到 O(nk),总复杂度 O(m \log m+2^knk\log n)。

注意到 Kruskal 的瓶颈在排序,考虑将子图的边先排序,枚举时归并优化。复杂度 O(m \log m+2^knk\alpha(n)),精细实现可以通过。

据说有 O(nk2^k) \sim O(n2^k) 做法,这也太牛了。

:::::

:::::info[代码]

const int N = 1e4 + 15, M = 1e6 + 5;
int n, m, k, c[15];
struct dsu {
    int fa[N], sz[N];
    void init() {iota(fa, fa + n+k + 1, 0), fill(sz, sz + n+k + 1, 1);}
    int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (sz[x] > sz[y]) swap(x, y);
        return fa[x] = y, sz[y] += sz[x], true;
    }
} U;
struct edge {
    int u, v, w;
    edge(int a = 0, int b = 0, int c = 0) : u(a), v(b), w(c) {}
    bool operator< (const edge& o) const {return w < o.w;}
} g[M], e[15][N], h[11*N], tmp[11*N];

void _main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) cin >> g[i].u >> g[i].v >> g[i].w;
    sort(g + 1, g + m + 1); U.init();
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        auto [u, v, w] = g[i];
        if (U.unite(u, v)) e[0][++cnt] = {u, v, w};
    }
    for (int i = 1; i <= k; i++) {
        cin >> c[i];
        for (int u = 1, w; u <= n; u++) cin >> w, e[i][u] = {i+n, u, w};
        sort(e[i] + 1, e[i] + n + 1);
    }
    i64 res = 1e18;
    for (int s = 0; s < (1 << k); s++) {
        copy(e[0] + 1, e[0] + n, h + 1);
        i64 cur = 0, cnt = n - 1;
        for (int i = 1; i <= k; i++) if (s >> (i - 1) & 1) {
            cur += c[i]; 
            merge(h + 1, h + cnt + 1, e[i] + 1, e[i] + n + 1, tmp + 1);
            cnt += n, copy(tmp + 1, tmp + cnt + 1, h + 1);
        }
        U.init();
        for (int i = 1; i <= cnt; i++) {
            auto [u, v, w] = h[i];
            if (U.unite(u, v)) cur += w;
        }
        chkmin(res, cur);
    }
    cout << res;
} 

:::::

CF2081D MST in Modulo Graph

给定 n 个点的完全图,边 (i,j) 的权值为 \max(a_i,a_j) \bmod \min(a_i,a_j)。求最小生成树边权和。

多测,\sum n, \sum \max a_i \le 5 \times 10^5,3 秒,500 MB。

ZR3598 没啥题

给定 n 个区间 [l_i,r_i],任意两个区间 (i,j) 有边,边权为 [l_i,r_i] \cap [l_j,r_j] 的长度。求最小生成树边权和。

多测,\sum n \le 2 \times 10^6,1 秒,512 MB。

:::::success[题解]

考察 Boruvka 的初轮,我们需要对每个区间 i 找到最小边对应的另一端点 j。边 (i,j) 的边权为

w(i,j)=\max(0,\min(r_i,r_j)-\max(l_i,l_j))

假定交集非空,对 \min 和 \max 分类讨论:

我们希望 w(i,j) 取极值,从而最优的 [l_j,r_j] 一定为以下三者之一:

这里我们丢掉 i \ne j 的限制,从而包含 w(i,j)=r_i-l_i 的情形。

考虑一轮 Boruvka 后得到的最小边。除 x 外的所有顶点,选出的最小边必然指向 x,y,z 之一。取出所有可能的最小边,画出边的导出子图:

我们注意到,这种形态的图只需要一轮 Boruvka 就能得到 MST!可以从三元环的情形类比过来。

于是直接找出每个区间的最小边相加即可,复杂度 O(n)。

:::::

:::::info[代码]

const int N = 2e6 + 5, inf = 1e9;
int n, l[N], r[N];
i64 f(int l1, int r1, int l2, int r2) {
    return max(0, min(r1, r2) - max(l1, l2));
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
    int x = max_element(l + 1, l + n + 1) - l;
    int y = min_element(r + 1, r + n + 1) - r;
    i64 z = inf;
    for (int i = 1; i <= n; i++) chkmin<i64>(z, r[i] - l[i]);
    i64 res = 0;
    for (int i = 1; i <= n; i++) {
        if (i == x) continue;
        res += min({z, f(l[i], r[i], l[x], inf), f(l[i], r[i], -inf, r[y])});
    }
    cout << res << '\n';
}

:::::

AT_cf17_final_j Tree MST

给定一棵 n 个点的无根树,边带权,第 i 个节点的点权为 a_i。

构造 n 个点的完全图,边 (u,v) 的权值为 a_u+a_v+\text{dis}(u,v),其中 \text{dis}(u,v) 为树链 u \to v 的边权和。求最小生成树边权和。

:::::success[题解]

任意定根后,记 d_u 为 u 根链的边权和,将 \text{dis}(u,v) 拆开:

w(u,v)=a_u+a_v+d_u+d_v-2d_{\text{lca}(u,v)}

令 a_u \gets a_u+d_u。考虑 Boruvka 的过程,我们需要为每个点 u 找到最小边 u \to v 使得 a_v-2d_{\text{lca}(u,v)} 最小。

转而枚举 x=\text{lca}(u,v),并在 x 子树内更新 u 的答案。这里我们不需要钦定 u,v 属于异侧子树,因为 d_x<d_{\text{lca}(u,v)} 导致在 x 处更新 (u,v) 不优,故不会被计入答案。

考虑做换根 DP:

还有一个约束需要考虑,上述过程最终求得的 u,v 有可能同属一个连通块,而我们要求 u,v 属于不同块。

解决方法是,我们同时记录最小值和次小值,并钦定最小值对应的 v 和次小值对应的 v 不在同块内。在 u 处更新答案时,如果 u 和最小值对应的 v 同块,就转而用次小值更新。

根据 Boruvka 进行 O(\log n) 轮,每轮复杂度线性,总复杂度 O(n \log n)。

:::::

:::::info[代码]

const int N = 2e5 + 5;
const i64 inf = 1e18;
i64 n, a[N], d[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<pair<int, int>> e[N];

void dfs1(int u, int fa) {
    for (auto [v, w] : e[u]) if (v != fa) d[v] = d[u] + w, dfs1(v, u);
}

using info = pair<i64, int>;  // (w, id)
struct node {
    info a, b; int c;
    node() : a(inf, -1), b(inf, -1), c(-1) {}
};
node operator+ (const node& x, const node& y) {
    node z;
    if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
    else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
    else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
    return z;
}

node f[N];
void dfs2(int u, int fa) {
    f[u].a = {a[u], u}, f[u].c = find(u);
    for (auto [v, w] : e[u]) if (v != fa) 
        dfs2(v, u), f[u] = f[u] + f[v];
}
void dfs3(int u, int fa) {
    for (auto [v, w] : e[u]) if (v != fa)
        f[v] = f[v] + f[u], dfs3(v, u);
}

info out[N];
i64 boruvka() {
    iota(fa + 1, fa + n + 1, 1);
    i64 res = 0;
    for (int cnt = 0; cnt < n - 1; ) {
        fill(f + 1, f + n + 1, node{}), fill(out + 1, out + n + 1, info{inf, -1});
        dfs2(1, -1);
        for (int u = 1; u <= n; u++) f[u].a.fi -= 2*d[u], f[u].b.fi -= 2*d[u];
        dfs3(1, -1);
        for (int u = 1; u <= n; u++) {
            info x = f[u].c == find(u) ? f[u].b : f[u].a;
            chkmin(out[find(u)], {x.fi + a[u], x.se});
        }
        for (int u = 1; u <= n; u++) {
            if (u != find(u) || out[u].se == -1) continue;
            int fu = u, fv = find(out[u].se);
            if (fu != fv) fa[fu] = fv, cnt++, res += out[u].fi;
        }
    }
    return res;
}

void _main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
    }
    dfs1(1, -1);
    for (int i = 1; i <= n; i++) a[i] += d[i];
    cout << boruvka();
} 

:::::

CF888G Xor-MST

给定 n 个顶点,第 i 个点的点权为 a_i。构造 n 个点的完全图,边 (u,v) 的权值为 a_u \oplus a_v。求最小生成树边权和。

:::::success[题解]

考虑 Boruvka,将问题转化成寻找最小边。

异或最优化问题,考虑自高位向低位建立 01-Trie。对全局维护 01-Trie T,再对每个连通块 x 维护 01-Trie T_x。

对 u 寻找最小边时,设 u 所属的连通块为 x,对 a_u 二进制分解后在 T-T_x 上贪心即可。具体地,我们维护子树 \text{size},对两棵 Trie 作差得到的树,尽量访问与 a_u 同位的边,除非子树 \text{size} 为 0。

合并两个连通块时,直接对 01-Trie 进行合并即可。维护信息需要 O(n \log V),从而总复杂度 O(n \log n \log V)。

注意 Boruvka 要求不出现边权相等的边。对于 a_u=a_v 的边,其权值为 0,可以将这些边缩起来,因此在读入后对 a_i 去重即可。

:::::

:::::info[代码]

const int N = 2e5 + 5, inf = 2e9;
using info = pair<int, int>;
int n, a[N], fa[N]; info out[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int tot, T[N], ch[2][65*N], cnt[65*N], id[65*N];
void pushup(int u) {cnt[u] = cnt[ch[0][u]] + cnt[ch[1][u]];}
void insert(int& u, int x, int p, int d = 30) {
    if (!u) u = ++tot;
    if (d < 0) return cnt[u]++, id[u] = p, void();
    insert(ch[x >> d & 1][u], x, p, d - 1), pushup(u);
}
int merge(int u, int v, int d = 30) {
    if (!u || !v) return u ? u : v;
    if (d < 0) return cnt[u] += cnt[v], u;
    ch[0][u] = merge(ch[0][u], ch[0][v], d - 1);
    ch[1][u] = merge(ch[1][u], ch[1][v], d - 1);
    return cnt[u] += cnt[v], u;
}
info ask(int u, int v, int x, int s = 0, int d = 30) {
    if (d < 0) return {s, id[u]};
    int t = x >> d & 1;
    if (cnt[ch[t][u]] - cnt[ch[t][v]]) return ask(ch[t][u], ch[t][v], x, s, d - 1);
    return ask(ch[t ^ 1][u], ch[t ^ 1][v], x, s | (1 << d), d - 1);
}

bool unite(int u, int v) {
    u = find(u), v = find(v);
    if (u == v) return false;
    return fa[v] = u, T[u] = merge(T[u], T[v]), true;
}

void _main() {
    cin >> n; iota(fa + 1, fa + n + 1, 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; i++) insert(T[0], a[i], i), insert(T[i], a[i], i);
    i64 res = 0;
    for (int cnt = 0; cnt < n-1; ) {
        fill(out + 1, out + n + 1, info{inf, -1});
        for (int u = 1; u <= n; u++) 
            chkmin(out[find(u)], ask(T[0], T[find(u)], a[u]));
        for (int u = 1; u <= n; u++) {
            if (u != find(u) || out[u].se == -1) continue;
            if (unite(u, out[u].se)) res += out[u].fi, cnt++;
        }
    } cout << res;
} 

:::::

CF2081D MST in Modulo Graph

给定 n 个点的完全图,边 (i,j) 的权值为 \max(a_i,a_j) \bmod \min(a_i,a_j)。求最小生成树边权和。

多测,\sum n, \sum \max a_i \le 5 \times 10^5,3 秒,500 MB。

:::::success[题解]

直接 Boruvka,问题变为给定 i 的颜色 c_i,对每个 i 找到 c_i \ne c_j 且 \max(a_i,a_j) \bmod \min(a_i,a_j) 最小的 j。

丢掉不同色的限制是套路的,维护最小值和次小值,并钦定二者颜色不同,信息构成交换半群。

设 x=\min(a_i,a_j),y=\max(a_i,a_j)。对 a_i 分讨:

注意实现细节,需要将值相等的 a_i 缩起来处理,复杂度才是调和型枚举的 O(V \log V)。

加上 boruvka 一只 \log 得到 O(n \log n\log V) 的复杂度,可以通过。

:::::

:::::info[代码]

const int N = 5e5 + 5, inf = 1e9;
int n, m, a[N], c[N], fa[N];
vector<int> pos[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    return fa[x] = y, true;
}

using info = pair<int, int>;   // (权值, 节点标号)
struct node {     // a 是最小值,b 是次小值
    info a, b; int c;
    node() : a(inf, -1), b(inf, -1), c(-1) {}
    node(info x) : a(x), b(inf, -1), c(find(x.se)) {}
    info get(int c0) {return c != c0 ? a : b;}
};
const node I{};
node operator+ (const node& x, const node& y) {
    // 半群复合
    if (x.a.se == -1) return y;
    if (y.a.se == -1) return x;
    node z;
    if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
    else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
    else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
    return z;
}
node operator- (node x, int k) {  // 权值 -k
    return x.a.fi -= k, x.b.fi -= k, x;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
node val[N], suf[N], wei[N];
// val[x]: a_i=x 的 i 信息并
// suf[x]: val 的后缀和
// wei[x]: 挂在 x 的 (-k, j) 信息并
info ans[N], out[N];
// ans[u]: 与节点 u 不同块的最小边
// out[u]: u 块向外的最小边

void solve() {
    fill(val + 1, val + m + 1, I);
    for (int i = 1; i <= n; i++) val[a[i]] += info(a[i], i);
    copy(val + 1, val + m + 1, suf + 1);
    for (int i = m-1; i >= 1; i--) suf[i] += suf[i+1];
    fill(ans + 1, ans + n + 1, info(inf, -1));
    for (int x = 1; x <= m; x++) {
        if (pos[x].empty()) continue;
        node cur = I;
        for (int k = x; k <= m; k += x) cur += suf[k] - k;
        for (int i : pos[x]) chkmin(ans[i], cur.get(find(i)));
    }
    fill(wei + 1, wei + m + 1, I);
    for (int x = 1; x <= m; x++) 
        for (int k = x; k <= m; k += x) wei[k] += val[x] - (x + k);
    node cur = I;
    for (int y = 1; y <= m; y++) {
        cur += wei[y];
        for (int i : pos[y]) {
            auto [w, j] = cur.get(find(i));
            chkmin(ans[i], info(w + y, j));
        }
    }
}

void _main() {
    cin >> n; iota(fa + 1, fa + n + 1, 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    m = *max_element(a + 1, a + n + 1);
    for (int i = 1; i <= m; i++) pos[i].clear();
    for (int i = 1; i <= n; i++) pos[a[i]].pb(i);
    i64 res = 0;
    for (int cnt = 0; cnt < n-1; ) {  // boruvka 过程
        solve();
        fill(out + 1, out + n + 1, info(inf, -1));
        for (int u = 1; u <= n; u++) chkmin(out[find(u)], ans[u]);
        for (int u = 1; u <= n; u++) {
            if (u != find(u)) continue;
            info q = out[u];
            if (unite(u, q.se)) cnt++, res += q.fi;
        }
    }
    cout << res << '\n';
} 

:::::

:::::success[另解]

对 x=\min(a_i,a_j) 考察区间 [kx,(k+1)x)。若区间中两数 y_1<y_2,必有 y_2 \bmod x >y_1 \bmod x。换言之,每个 [kx,(k+1)x) 只有最小值有用。

将点权相同的点缩起来处理,复杂度是调和型枚举,只会建 O(V \log V) 条边。视 n,V 同阶,Kruskal 即可做到 O(n \log^2 n),精细实现可以 1log。

:::::

P9701 [GDCPC 2023] Classic Problem

构造 n 个点的完全图,其中 m 条特殊边的边权给定,剩余边 (i,j) 的权值为 |i-j|。求最小生成树边权和。

多测,n \le 10^9,m \le 10^5,\sum m \le 5 \times 10^5,8 秒,1024 MB。

:::::success[题解]

将特殊边的端点记为特殊点。在数轴上考虑问题,对于两个相邻的特殊点 x,y,容易发现 (x,y) 内的点一定连成一条链。

我们将 (x,y) 缩成一个点,并将答案加上链的权值和。这样图就只有 2m 个顶点了。

考虑 Boruvka。对于点 u,从 u 向外的最小边必然为以下三者之一:

特殊边容易处理。后两种情形是对称的,这里只说明左侧点如何处理。

我们在 Boruvka 的每轮中,维护 f_u 表示 u 左侧最近的异块点 v。查询时从 v \gets f_v 开始,若 u \to v 有特殊边则令 v \gets v-1,若 u,v 同块则令 v \gets f_v,直到 v 合法。

考虑特殊边只有 m 条边,故 v \gets v-1 操作总共 m 次,均摊下来每轮复杂度线性。总复杂度 O(m \log m)。

:::::

:::::info[代码]

const int N = 4e5 + 5, inf = 2e9;
int n, m, k, a[N], fa[N], lo[N], hi[N], f[N], g[N], pos[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<pair<int, int>> e[N];
set<pair<int, int>> S;
vector<tuple<int, int, int>> vec;
umap<int, int> mp;
using info = pair<int, int>;  // (w, id)
info out[N];

void _main() {
    S.clear(), vec.clear(), mp.clear();
    for (int i = 1; i <= k; i++) e[i].clear();
    cin >> n >> m; 
    a[1] = 1, a[2] = n, n = 2, k = 0;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w;
        vec.emplace_back(u, v, w);
        a[++n] = u, a[++n] = v;
    }
    i64 res = 0; 
    sort(a + 1, a + n + 1), n = unique(a + 1, a + n + 1) - a - 1;
    mp[a[1]] = ++k, lo[k] = hi[k] = a[1];
    for (int i = 2; i <= n; i++) {
        int x = a[i - 1], y = a[i];
        if (y - x > 1) res += y - x - 2, k++, lo[k] = x + 1, hi[k] = y - 1;
        mp[a[i]] = ++k, lo[k] = hi[k] = a[i];
    }
    for (auto [u, v, w] : vec) {
        u = mp[u], v = mp[v];
        e[u].emplace_back(v, w), e[v].emplace_back(u, w);
        S.emplace(u, v), S.emplace(v, u);
    }
    iota(fa + 1, fa + k + 1, 1);
    for (int cnt = 0; cnt < k-1; ) {
        fill(f + 1, f + k + 1, 0), fill(g + 1, g + k + 1, k+1), fill(out + 1, out + k + 1, info{inf, -1});
        for (int i = 2; i <= k; i++) {
            if (find(i) == find(i - 1)) f[i] = f[i - 1];
            else f[i] = i - 1;
        }
        for (int i = k - 1; i >= 1; i--) {
            if (find(i) == find(i + 1)) g[i] = g[i + 1];
            else g[i] = i + 1;
        }
        for (int u = 1; u <= k; u++) 
            for (auto [v, w] : e[u]) 
                if (find(u) != find(v)) chkmin(out[find(u)], info{w, v});
        for (int u = 1; u <= k; u++) {
            int v = f[u];
            while (v >= 1) {
                if (!S.count(make_pair(u, v))) break;
                if (--v >= 1 && find(u) == find(v)) v = f[v];
            } 
            if (v >= 1) chkmin(out[find(u)], info{lo[u] - hi[v], v});
        }
        for (int u = 1; u <= k; u++) {
            int v = g[u];
            while (v <= k) {
                if (!S.count(make_pair(u, v))) break;
                if (++v <= k && find(u) == find(v)) v = g[v];
            } 
            if (v <= k) chkmin(out[find(u)], info{lo[v] - hi[u], v});
        }
        for (int u = 1; u <= k; u++) {
            if (u != find(u) || out[u].se == -1) continue;
            int fu = u, fv = find(out[u].se);
            if (fu != fv) fa[fv] = fu, cnt++, res += out[u].fi;
        }
    }
    cout << res << '\n';
}

:::::

P11134 【MX-X5-T6】「GFOI Round 1」Abiogenesis

给定 n 条线段 [l_i,r_i],第 i 条线段的权值为 (a_i,b_i)。

构造无向图 G,对所有 1 \le i<j \le n,若 [l_i,r_i] \cap [l_j,r_j ]\ne \varnothing,则连边 (i,j),边权为 a_i+a_j+|b_i-b_j|。求 G 最小生成树边权和,或报告 G 不连通。

多测,\sum n \le 10^5,5 秒,512 MB。

:::::success[题解]

考虑优化 Boruvka 寻找最小边的过程。设第 i 个顶点所属的连通块为 c_i,则我们要对每个 i 找到一个 j 满足:

注意到 AT_cf17_final_j 的 trick,我们同时记录最小值和次小值,并钦定二者对应的 c_i 不同。这样就能去掉 c_i \ne c_j 的限制。

接下来,尝试对绝对值分类讨论。这里以 b_i \le b_j 为例,限制为:

按 b_i 降序排序,则 j 是 j \in [1,i) 中满足 [l_i,r_i] \cap [l_j,r_j ]\ne \varnothing 且 a_j+b_j 取 \min 的 j。拆掉 [l_i,r_i] \cap [l_j,r_j ]\ne \varnothing 就变成三维偏序,复杂度 3log 难以通过。

取巧的方法是,直接将 a_j+b_j 的点权挂在 [l_j,r_j] 上,查询求 [l_i,r_i] 中权值的 \min。容易理解正确性。

用线段树维护即可,总复杂度 O(n \log^2 n)。

本题极度卡常。下面放的是被卡常的代码,扔给 GPT5.6 卡到了 4.58s 通过。

:::::

:::::info[代码]

const int N = 2e5 + 5, inf = 1e9;
int n, m, d[N], fa[N], sz[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) swap(x, y);
    return fa[x] = y, sz[y] += sz[x], true; 
}
struct seg {
    int l, r, a, b, id;
} a[N];

using info = pair<int, int>;
struct node {
    info a, b; int c;
    node() : a(inf, -1), b(inf, -1), c(-1) {}
    node(int w, int id) : a(w, id), b(inf, -1), c(find(id)) {}
};
const node I{};
node operator+ (const node& x, const node& y) {
    if (x.a.se == -1) return y;
    if (y.a.se == -1) return x;
    node z;
    if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
    else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
    else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
    return z;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
info out[N];

struct segtree {
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    node val[4*N], tag[4*N];
    void pushup(int rt) {val[rt] = val[ls] + val[rs] + tag[rt];}
    void build(int l = 1, int r = m, int rt = 1) {
        val[rt] = tag[rt] = I;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs);
    }
    void update(int tl, int tr, const node& c, int l = 1, int r = m, int rt = 1) {
        if (tl <= l && r <= tr) return val[rt] += c, tag[rt] += c, void();
        int mid = (l + r) >> 1; 
        if (tl <= mid) update(tl, tr, c, l, mid, ls);
        if (tr > mid) update(tl, tr, c, mid + 1, r, rs);
        pushup(rt);
    }
    node ask(int tl, int tr, int l = 1, int r = m, int rt = 1) {
        if (tl <= l && r <= tr) return val[rt];
        int mid = (l + r) >> 1; node res = tag[rt];
        if (tl <= mid) res += ask(tl, tr, l, mid, ls);
        if (tr > mid) res += ask(tl, tr, mid + 1, r, rs);
        return res;
    }
} T;

void _main() {
    read(n), m = 0;
    for (int i = 1; i <= n; i++) {
        read(a[i].l, a[i].r, a[i].a, a[i].b), a[i].id = i;
        d[++m] = a[i].l, d[++m] = a[i].r;
    }
    sort(d + 1, d + m + 1), m = unique(d + 1, d + m + 1) - d - 1;
    for (int i = 1; i <= n; i++) {
        a[i].l = lower_bound(d + 1, d + m + 1, a[i].l) - d;
        a[i].r = lower_bound(d + 1, d + m + 1, a[i].r) - d;
    }
    sort(a + 1, a + n + 1, [](const seg& x, const seg& y) -> bool {
        return x.b > y.b;
    });
    iota(fa + 1, fa + n + 1, 1), fill(sz + 1, sz + n + 1, 1);
    i64 res = 0;
    for (int cnt = 0; cnt < n-1; ) {
        fill(out + 1, out + n + 1, info{inf, -1});
        T.build();
        for (int i = 1; i <= n; i++) {
            node x = T.ask(a[i].l, a[i].r);
            if (x.a.se != -1) x.a.fi += a[i].a - a[i].b;
            if (x.b.se != -1) x.b.fi += a[i].a - a[i].b;
            chkmin(out[find(a[i].id)], x.c == find(a[i].id) ? x.b : x.a);
            T.update(a[i].l, a[i].r, node(a[i].a + a[i].b, a[i].id));
        }
        T.build();
        for (int i = n; i >= 1; i--) {
            node x = T.ask(a[i].l, a[i].r);
            x.a.fi += a[i].a + a[i].b, x.b.fi += a[i].a + a[i].b;
            chkmin(out[find(a[i].id)], x.c == find(a[i].id) ? x.b : x.a);
            T.update(a[i].l, a[i].r, node(a[i].a - a[i].b, a[i].id));
        }
        for (int u = 1; u <= n; u++) {
            if (u != find(u)) continue;
            if (out[u].se == -1) return cout << -1 << '\n', void();
            if (unite(u, out[u].se)) cnt++, res += out[u].fi;
        }
    }
    cout << res << '\n';
} 

:::::

P6199 [EER1] 河童重工

给定两棵 n 个节点的无根树 T_1,T_2,边带权。

构造 n 个点的完全图,边 (u,v) 的权值为 \text{dis}_1(u,v)+\text{dis}_2(u,v)。求最小生成树边权和。

:::::success[题解]

考虑优化 Boruvka 寻找最小边的过程。我们需要为所有顶点 u 找到不同块点 v,使得 \text{dis}_1(u,v)+\text{dis}_2(u,v) 最小。

套路地记录最小值和次小值,并钦定二者不同块,则 v 的异块限制可以丢掉。

任意定根后,在 T_1 上枚举 x=\text{lca}_1(u,v)。可以说明若 \text{lca}_1(u,v) 比枚举的 x 更深,则在 x 处统计贡献不优,从而限制弱化为 u,v \in \text{subtree}_1(x)。记 d_u=\text{dis}_1(x,u),则 \text{dis}_1(u,v)=d_u+d_v。

对点集 S=\text{subtree}_1(x),考虑建出 S 在 T_2 上的虚树 T_x。对 T_2 求出 u 根链的权值和 b_u,在 T_x 上枚举 y=\text{lca}_2(u,v),所求为最小的

d_u+d_v+\text{dis}_2(u,v)=d_u+d_v+b_u+b_v-2b_y

限制同理放宽为 u,v \in \text{subtree}_2(y)。做类似 AT_cf17_final_j 的换根 DP,第一次自底向上将 (u,v) 的贡献挂到 y 上,第二次自顶向下将 y 处的贡献下放到具体的 u 处。

复杂度与每轮建立的 T_x 节点数目和相关。可以在 T_1 上点分治,将 x 不断选取为当前子树的重心,这样 T_x 的总节点数是 O(n \log n) 级别的。

Boruvka,点分治,建虚树各一只 \log,总复杂度 3log。注意到 T_1 是静态的,从而虚树形态固定,在 T_1 的点分树上预处理虚树的形态后,做 Boruvka 时只要遍历点分树,对虚树做线性的换根 DP。

正确实现的复杂度为 O(n \log^2 n)。

:::::

:::::info[代码]

const int N = 1e5 + 5, inf = 2e9;
int n, a[N], b[N], w[N], fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool unite(int x, int y) {
    x = find(x), y = find(y);
    return x == y ? false : (fa[x] = y, true);
}
vector<pair<int, int>> e1[N], e2[N];

void dfs1(int u, int fa) {
    for (auto [v, w] : e1[u]) if (v != fa) a[v] = a[u] + w, dfs1(v, u);
}

int dn, dfn[N], st[18][N];
int cmp(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
int lca(int u, int v) {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int k = lg(v - u++);
    return cmp(st[k][u], st[k][v - (1 << k) + 1]);
}
void dfs2(int u, int fa) {
    dfn[u] = ++dn, st[0][dn] = fa;
    for (auto [v, w] : e2[u]) if (v != fa) b[v] = b[u] + w, dfs2(v, u);
}

int del[N], sz[N];
void dfs3(int u, int fa) {
    sz[u] = 1;
    for (auto [v, w] : e1[u]) if (v != fa && !del[v]) dfs3(v, u), sz[u] += sz[v];
}
int dfs4(int u, int fa, int n) {
    for (auto [v, w] : e1[u]) if (v != fa && !del[v] && sz[v] > n/2) return dfs4(v, u, n);
    return u;
}
void dfs5(int u, int fa, i64 d, vector<pair<int, i64>>& a) {
    a.emplace_back(u, d);
    for (auto [v, w] : e1[u]) if (v != fa && !del[v]) dfs5(v, u, d + w, a);
}

vector<int> ctr;
int rt[N];
vector<pair<int, int>> ege[N];
vector<pair<int, i64>> sub[N];
vector<int> ver[N];
void build(int u) {
    dfs3(u, -1); int x = dfs4(u, -1, sz[u]); 
    ctr.emplace_back(x);
    dfs5(x, -1, 0, sub[x]);
    vector<int>& s = ver[x]; 
    for (auto [u, d] : sub[x]) s.emplace_back(u);
    auto cmp = [&](int x, int y) -> bool {
        return dfn[x] < dfn[y];
    };
    sort(s.begin(), s.end(), cmp); int m = s.size();
    for (int i = 1; i < m; i++) s.emplace_back(lca(s[i-1], s[i]));
    sort(s.begin(), s.end(), cmp), s.erase(unique(s.begin(), s.end()), s.end());
    rt[x] = s[0]; 
    for (int i = 1; i < (int)s.size(); i++) {
        int f = lca(s[i-1], s[i]);
        ege[x].emplace_back(f, s[i]);
    }
    del[x] = true;
    for (auto [y, w] : e1[x]) if (!del[y]) build(y);
}

void prework() {
    iota(fa + 1, fa + n + 1, 1);
    dfs1(1, -1), dfs2(1, 0);
    for (int i = 1; i <= n; i++) w[i] = a[i] + b[i];
    for (int i = 1; (1 << i) <= n; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            st[i][j] = cmp(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    build(1);
}

using info = pair<i64, int>;  // (w, id)
struct node {
    info a, b; int c;
    node() : a(inf, -1), b(inf, -1), c(-1) {}
    node(int u, i64 w) : a(w, u), b(inf, -1), c(find(u)) {}
} f[N];
node operator+ (const node& x, const node& y) {
    node z;
    if (x.c == y.c) z.a = min(x.a, y.a), z.b = min(x.b, y.b), z.c = x.c;
    else if (x.a <= y.a) z.a = x.a, z.b = min(x.b, y.a), z.c = x.c;
    else z.a = y.a, z.b = min(y.b, x.a), z.c = y.c;
    return z;
}
node& operator+= (node& x, const node& y) {return x = x + y;}
node add(node x, int d) {
    if (x.a.se != -1) x.a.fi += d;
    if (x.b.se != -1) x.b.fi += d;
    return x;
}
info out[N];

vector<int> e3[N];
void dfs5(int u) {
    for (int v : e3[u]) dfs5(v), f[u] += add(f[v], b[v] - b[u]);
}
void dfs6(int u) {
    for (int v : e3[u]) f[v] += add(f[u], b[v] - b[u]), dfs6(v);
}

void _main() {
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e1[u].emplace_back(v, w), e1[v].emplace_back(u, w);
    }
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        e2[u].emplace_back(v, w), e2[v].emplace_back(u, w);
    }
    prework();
    i64 res = 0;
    for (int cnt = 0; cnt < n-1; ) {
        fill(out + 1, out + n + 1, info{inf, -1});
        for (int x : ctr) {
            for (int u : ver[x]) f[u] = node(), e3[u].clear();
            for (auto [u, d] : sub[x]) f[u] = node(u, d);
            for (auto [u, v] : ege[x]) e3[u].emplace_back(v);
            dfs5(rt[x]), dfs6(rt[x]);
            for (auto [u, d] : sub[x]) {
                node q = add(f[u], d);
                chkmin(out[find(u)], q.c == find(u) ? q.b : q.a);
            }
        }
        for (int u = 1; u <= n; u++) {
            if (u != find(u) || out[u].se == -1) continue;
            if (unite(u, out[u].se)) cnt++, res += out[u].fi; 
        }
    } cout << res;
}

:::::

P4768 [NOI2018] 归程

给定 n 个点 m 条边的无向连通图,边有两种权值 l_i,a_i。

多测,$T \le 3$,$n \le 2 \times 10^5$,$m,q \le 4 \times 10^5$,4 秒,512 MB。

:::::success[题解] 对于 u,v,u \to v 在 a_i 上可达的充要条件为两点之间最大瓶颈路的权值 >k。

考虑对 a_i 求最大生成树,建立 Kruskal 重构树。这样 u \to v 可达当且仅当其 LCA 点权 >k。

从 1 开始关于 l_i 跑 Dijkstra,求出每个点到 1 的最短路。

只需求出最浅的 u 的祖先,满足其祖先的点权 >k,则祖先对应子树中叶子的最短路 \min 即为答案。第一步树上倍增,第二步 DFS 预处理。

视 n,q,m 同阶复杂度 O(n \log n)。

:::::info[代码]

const int N = 4e5 + 5;
using edge3 = tuple<int, int, int>;
i64 n, m, q, op, s;
vector<pair<int, i64>> el[N];
vector<edge3> ea;
i64 dis[N];

struct node {
    int v; i64 w;
    node(int a = 0, i64 b = 0) : v(a), w(b) {}
    bool operator< (const node& a) const {return w > a.w;}
}; 
void dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<node> q;
    dis[s] = 0, q.emplace(s, 0);
    while (!q.empty()) {
        auto [u, d] = q.top(); q.pop();
        if (d != dis[u]) continue;
        for (auto [v, w] : el[u]) {
            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w, q.emplace(v, dis[v]);
        }
    }
}

int tot, fa[N], wei[N], f[20][N];
i64 val[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<int> et[N];
void kruskal() {
    for (int i = 1; i <= 2 * n; i++) et[i].clear();
    iota(fa + 1, fa + 2 * n + 1, 1), tot = n;
    sort(ea.begin(), ea.end(), greater<edge3>());
    for (auto [w, u, v] : ea) {
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fa[fv] = ++tot, wei[tot] = w;
        et[tot].emplace_back(fu), et[tot].emplace_back(fv);
    }
}

void dfs(int u) {
    if (et[u].empty()) return val[u] = dis[u], void();
    for (int v : et[u]) f[0][v] = u, dfs(v), chkmin(val[u], val[v]); 
}
i64 ask(int u, int k) {
    for (int i = lg(tot); i >= 0; i--) {
        if (f[i][u] && wei[f[i][u]] > k) u = f[i][u];
    } return val[u];
}

void _main() {
    cin >> n >> m; ea.clear();
    for (int i = 1; i <= n; i++) el[i].clear();
    for (int i = 1, u, v, l, a; i <= m; i++) {
        cin >> u >> v >> l >> a;
        el[u].emplace_back(v, l), el[v].emplace_back(u, l);
        ea.emplace_back(a, u, v);
    }
    dijkstra(1), kruskal();
    memset(val, 0x3f, sizeof(val)), f[0][tot] = 0, dfs(tot);
    for (int i = 1; (1 << i) <= tot; i++)
        for (int j = 1; j <= tot; j++) f[i][j] = f[i - 1][f[i - 1][j]];
    cin >> q >> op >> s;
    for (i64 u, k, last = 0; q--; ) {
        cin >> u >> k;
        u = (u + op * last - 1) % n + 1;
        k = (k + op * last) % (s + 1);
        cout << (last = ask(u, k)) << '\n';
    }
} 

:::::

P6765 [APIO2020] 交换城市

给定 n 个点 m 条边的无向带权连通图。

$n \le 10^5$,$m,q \le 2 \times 10^5$,1.5 秒,512 MB。

:::::success[题解] 先考虑怎么判定有解。经过思考,我们发现 u,v 可以交换的情况有如下两种:

情况一:环

如图所示,此时 1,2 互换位置可以令 1 \to 3, 2 \to 1, 3 \to 2。

情况二:三度点

如图所示,此时 1,2 互换位置借助一个 \ge 3 度的点 3,令 1 \to 3 \to 4, 2 \to 3 \to 1, 1 \to 3。

概括一下,只要 u,v 所在连通块非链即可。于是我们会了怎么判定无解。

考虑带权并查集,记录 c_{1/2,x} 表示 x 集合内 1/2 度点的数目,s_x 表示 x 集合的大小,则 x 集合为链当且仅当 c_{1,x}=2 \land c_{1,x}+c_{2,x}=s_x。

定义 h_x 为:x 在 Kruskal 重构树上的祖先中,深度最深的非链连通块代表元。我们首先要解决如果判定连通块是否为链,这样一次 DFS 即可处理得到 h_x。

在原本的重构树上,u,v 之间的瓶颈路为 LCA 的点权。而现在引入 h_x 的目的即为修正 LCA 的答案,即 h_{\text{lca}} 作为最终答案。这样我们就解决了 \ge 3 度点对答案的影响。

考虑环的问题如何解决,可以魔改一下 Kruskal 重构树的形态。在 Kruskal 过程中,若 u,v 同属一个集合说明 u \to v 是环上的一条边。求出 u,v 的代表元 x 以后,单独建一个新点并将 x 挂到儿子上,新点的点权为 (u,v) 的边权。

在查询时,LCA 上方额外多出一个新点,因此环的情形也能被 h_x 修正。这样就做完了,视 n,m,q 同阶复杂度 O(n \log n)。

:::::info[代码]

const int N = 3e5 + 5;
int n, m, tot, wei[N], deg[N], fa[N], c1[N], c2[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<tuple<int, int, int>> e;
vector<int> et[N];

void upd(int u, int x) {
    if (deg[u] == 1) c1[find(u)] += x;
    if (deg[u] == 2) c2[find(u)] += x;
}

int h[N], f[N], sz[N], son[N], dep[N], top[N];
void dfs1(int u) {
    if (c1[u] == 2 && c1[u] + c2[u] == sz[u]) h[u] = h[f[u]];
    else h[u] = u;
    sz[u] = 1; 
    for (int v : et[u]) {
        dep[v] = dep[u] + 1, f[v] = u, dfs1(v), sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int v : et[u]) if (v != son[u]) dfs2(v, v);
}
int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = f[top[u]];
    } return dep[u] < dep[v] ? u : v;
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    ::n = N, ::m = M;
    for (int i = 0; i < m; i++) e.emplace_back(W[i], U[i] + 1, V[i] + 1);
    sort(e.begin(), e.end());
    iota(fa + 1, fa + n + m + 1, 1), fill(sz + 1, sz + n + 1, 1), tot = n;
    for (auto [w, u, v] : e) {
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            wei[++tot] = w;
            sz[tot] = sz[fu] + sz[fv], c1[tot] = c1[fu] + c1[fv], c2[tot] = c2[fu] + c2[fv];
            fa[fu] = fa[fv] = tot;
            et[tot].emplace_back(fu), et[tot].emplace_back(fv);
        } else if (wei[fu] != w) {
            wei[++tot] = w;
            sz[tot] = sz[fu], c1[tot] = c1[fu], c2[tot] = c2[fu];
            fa[fu] = tot, et[tot].emplace_back(fu);
        }
        upd(u, -1), upd(v, -1);
        deg[u]++, deg[v]++;
        upd(u, 1), upd(v, 1);
    }
    dfs1(tot), dfs2(tot, tot);
} 

int getMinimumFuelCapacity(int X, int Y) {
    int u = X + 1, v = Y + 1, p = lca(u, v);
    return h[p] ? wei[h[p]] : -1;
}

:::::

P13342 [EGOI 2025] Wind Turbines / 风力涡轮机

给定 n 个点 m 条边的无向带权图。

$n,m \le 10^5$,$q \le 2 \times 10^5$,4 秒,1024 MB。

:::::success[题解] 问题容易描述为:每个询问给出 l,r,建立虚点 S 并连边 \forall i \in [l,r],S \leftrightarrow i,边权为 0,然后求新图上 MST 边权和。

考虑特殊性质,即 r-l=1 的情形。此时 l \to r 路径上边权最大的边会被删去。因此问题等价于最小瓶颈路,建立最小生成树的 Kruskal 重构树以后求 LCA 点权即可。

将上述观察扩展到一般情况。记 k=r-l+1,则对于 [l,r],其两两路径上的最大瓶颈边需要被删去,取出前 k-1 大删去即可。在 Kruskal 重构树上刻画,即对于 [l,r] 中的节点求出两两 LCA 点权的前 k-1 大和,然后原图 MST 边权和减去这个值即为答案。

这里需要说明一点,前 k-1 大的 LCA 点权必须来自不同的 LCA。事实上,考虑建出这 k 个叶子的虚树,则虚树上的非叶节点恰好对应了这 k-1 个点。

类似 NOIP2024 T4 的结论,可以将所求转化成 \sum \limits_{i=l}^{r-1} f(\text{LCA}(i,i+1)),其中 f(i) 表示点权。分析到这里可以通过 subtask 5。

考虑节点 u,其被计入答案,当且仅当存在左子树节点 x,右子树节点 y,满足 l \le \min(x,y) < \max(x,y) \le r,则点 u 产生 f(u) 的贡献。观察子树 u 中的两个点对 (x_1,y_1) 和 (x_2,y_2),若 [x_1,y_1] \subseteq [x_2,y_2],则 (x_1,y_1) 必然比 (x_2,y_2) 更早满足条件,即 (x_2,y_2) 无用。因此只需求出所有极小区间,也就是第一类支配点对。

可以用 set 配合 dsu on tree 求出所有支配对。详细的求法见这篇题解。

现在问题转化为:有 O(n \log n) 个点对 (x_i,y_i)。q 次询问给出 [l,r],查询有多少个点 u 满足其名下至少存在一个点对 [x_i,y_i] \subseteq [l,r],若存在则加上 f(u)。不妨将 u 视为点对颜色,问题就是数颜色。

转 l-r 二维平面分析,一次查询就是给出一个以 (l,r) 为左上顶点的 2-side 矩形,求矩形内所有颜色的权值和。

考虑扫描线。固定直线 x=l,对于颜色 u,若它在 x \ge l 的区域内存在多个点,则只需保留 y 坐标最低的点以落入 y \le r 的询问区域。因此记 h_u 为当前 x \ge l 且颜色为 u 的点对的 y_{\min}。在 x 轴上降序扫描线,并对 y 轴开树状数组,坐标 y 处维护 \sum \limits_{h_u =y} f(u)。询问只需在树状数组上求前缀和。

至此问题解决。视 n,m,q 同阶复杂度 O(n \log^2 n)。

:::::info[代码]

const int N = 2e5 + 5;
int n, m, q, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
struct BIT {
    i64 tr[N];
    void add(int x, i64 c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    i64 ask(int x) {
        i64 res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} T;

vector<tuple<int, int, int>> ed;
int tot, f[N]; i64 mst;
vector<int> e[N];
void kruskal() {
    sort(ed.begin(), ed.end()), tot = n;
    iota(fa + 1, fa + 2 * n + 1, 1);
    for (auto [w, u, v] : ed) {
        int fu = find(u), fv = find(v);
        if (fu == fv) continue;
        fa[fu] = fa[fv] = ++tot, mst += w, f[tot] = w;
        e[tot].emplace_back(fu), e[tot].emplace_back(fv);
    }
}

using node = pair<int, int>;
set<int> st[N];
vector<node> p[N];
void dfs(int u) {
    if (u <= n) return st[u].emplace(u), void();
    for (int v : e[u]) {
        dfs(v);
        if (st[u].size() < st[v].size()) swap(st[u], st[v]);
        for (int x : st[v]) {
            auto it = st[u].lower_bound(x);
            if (it != st[u].end()) p[x].emplace_back(u, *it);
            if (it != st[u].begin()) it--, p[*it].emplace_back(u, x);
        }
        for (int x : st[v]) st[u].emplace(x);
    }
}

i64 h[N], ans[N];
vector<node> qry[N];

void _main() {
    cin >> n >> m >> q;
    for (int i = 1, u, v, w; i <= m; i++) {
        cin >> u >> v >> w; u++, v++;
        ed.emplace_back(w, u, v);
    }
    kruskal();
    for (int i = 1; i <= tot; i++) if (i == fa[i]) dfs(i);
    for (int i = 1, l, r; i <= q; i++) {
        cin >> l >> r; l++, r++;
        qry[l].emplace_back(r, i);
    }
    fill(h + 1, h + tot + 1, n + 1);
    for (int i = n; i >= 1; i--) {
        for (auto [x, y] : p[i]) {
            if (y >= h[x]) continue;
            T.add(h[x], -f[x]);
            h[x] = y, T.add(h[x], f[x]);
        }
        for (auto [j, id] : qry[i]) ans[id] = T.ask(j);
    }
    for (int i = 1; i <= q; i++) cout << mst - ans[i] << '\n';
} 

:::::

CF1797F Li Hua and Path

给定一棵节点数为 n 的无根树。称点对 (u,v) 是好的,当且仅当 u<v 且下列两个条件恰好有一个为真:

你需要支持 q 次加叶子,保证叶子的标号最大,在操作前和每次操作后求出好点对的数目。

:::::success[题解] 先考虑没询问咋做,并且假定你不会淀粉质。

考虑容斥。记满足第一个条件的点对集合为 A,第二个条件的集合为 B,则答案为 |A|+|B|-2|A \cap B|。

先计算 |A| 和 |B|。注意到约束是一个类似点权瓶颈路的形式,因此考虑类似 Kruskal 重构树的手法。具体地,我们从大到小扫描节点 u,并考虑其邻居 v。若 v>u,则说明 v 已经被处理过,此时将 u 和 v 所属集合的代表元连边。

在普通的 Kruskal 重构树中,我们在集合合并时要建一个虚点,形成一棵二叉树。而这里建出的则是关于点权的多叉树,因此这个东西也叫做多叉重构树。

在上述流程建出的树中,u 的编号一定小于其子树内的所有节点。因此,在这棵树中,u 到其任意后代的路径上,u 一定是最小值。

事实上,一条属于集合 A 的路径在这棵树上就是一条向下的路径。称这棵树为 T_{\min},在路径的上端点处统计贡献,|A| 即为子树大小之和。同理建立 T_{\max} 后可以求出 |B|。

在重构树上刻画,则 (u,v) \in (A \cap B) 当且仅当在 T_{\min} 中 v 是 u 的后代,在 T_{\max} 中 u 是 v 的后代。我们考虑求出 T_{\max} 上的 DFS 序,然后在 T_{\min} 上 DFS 统计,只需要一个树状数组配合。

考虑加叶子怎么处理。此时这个节点 u 是 T_{\min} 的叶子,T_{\max} 的根。维护答案的变化量:

根据容斥公式得到答案 d_u+|T_{\max}|-2d_u=|T_{\max}|-d_u。维护深度即可。

复杂度 O(n \log n+q)。

:::::info[代码]

const int N = 4e5 + 5;
int n, q, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
vector<int> e[N], emx[N], emn[N];
int dn, sz[N], dfn[N], cnt[N], dep[N];

void dfs1(int u) {
    sz[u] = 1, dfn[u] = ++dn;
    for (int v : emx[u]) dfs1(v), sz[u] += sz[v];
}
void dfs2(int u) {
    cnt[u] = 1;
    for (int v : emn[u]) dep[v] = dep[u] + 1, dfs2(v), cnt[u] += cnt[v];
} 
struct BIT {
    i64 tr[N];
    void add(int x, int c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    i64 ask(int x) {
        i64 res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
    i64 ask(int l, int r) {return ask(r) - ask(l - 1);}
} T;
i64 dfs3(int u) {
    i64 res = T.ask(dfn[u], dfn[u] + sz[u] - 1);
    T.add(dfn[u], 1);
    for (int v : emn[u]) res += dfs3(v);
    T.add(dfn[u], -1);
    return res;
}

void _main() {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        e[u].emplace_back(v), e[v].emplace_back(u);
    }
    cin >> q; iota(fa + 1, fa + n + 1, 1);
    for (int u = 1; u <= n; u++) for (int v : e[u]) {
        int fu = find(u), fv = find(v);
        if (v < u && fu != fv) emx[u].emplace_back(fv), fa[fv] = fu;
    }
    iota(fa + 1, fa + n + 1, 1);
    for (int u = n; u >= 1; u--) for (int v : e[u]) {
        int fu = find(u), fv = find(v);
        if (v > u && fu != fv) emn[u].emplace_back(fv), fa[fv] = fu;
    }
    dfs1(n), dfs2(1);
    i64 res = accumulate(sz + 1, sz + n + 1, 0LL);
    res += accumulate(cnt + 1, cnt + n + 1, 0LL);
    res -= 2 * dfs3(1), res -= 2 * n;
    cout << res << '\n';
    for (int i = 1, u; i <= q; i++) {
        cin >> u, dep[i + n] = dep[u] + 1;
        res += n + i - dep[i + n] - 1;
        cout << res << '\n';
    }
} 

:::::

P2619 [国家集训队] Tree I

给定 n 个点 m 条边的无向带权连通图,每条边有黑白两色。求恰好有 k 条白色边的生成树中,边权和最小的生成树,并输出答案。

:::::success[题解]

我们声称答案关于 k 下凸。

考虑 WQS 二分斜率 a,相当于给每条白边带 +a 的额外代价。此时求出最小生成树中的白边数目,即可决策二分方向。

注意到二分时只要合并黑边和白边两个有序数组,可以归并优化,做到 O(m \alpha(n)\log V)。

类似题目是 P5633。两个题的注意事项可以参见讨论区。

:::::

:::::info[代码]

const int N = 1e5 + 5;
int n, m, k, c0, c1, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
struct edge {
    int u, v, w, col;
    bool operator< (const edge& e) const {
        return w != e.w ? w < e.w : col < e.col;
    }
} a[N], b[N], c[N];

void _main() {
    cin >> n >> m >> k;
    for (int i = 1, u, v, w, c; i <= m; i++) {
        cin >> u >> v >> w >> c; u++, v++;
        if (c == 0) a[++c0] = {u, v, w, c};
        else b[++c1] = {u, v, w, c};
    }
    sort(a + 1, a + c0 + 1), sort(b + 1, b + c1 + 1);
    int l = -100, r = 100, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1, sum = 0, cnt = 0;
        auto check = [&]() -> void {
            iota(fa + 1, fa + n + 1, 1);
            for (int i = 1; i <= c0; i++) a[i].w += mid;
            merge(a + 1, a + c0 + 1, b + 1, b + c1 + 1, c + 1);
            for (int i = 1; i <= m; i++) {
                int fu = find(c[i].u), fv = find(c[i].v);
                if (fu == fv) continue;
                fa[fu] = fv, sum += c[i].w;
                if (c[i].col == 0) cnt++; 
            }
            for (int i = 1; i <= c0; i++) a[i].w -= mid;
        };
        check();
        if (cnt >= k) l = mid + 1, res = sum - k * mid;
        else r = mid - 1;
    }
    cout << res;
}

:::::

CF1054G New Road Network

现有 n 个点和 m 个集合 S_i,构造一棵 n 个点的树 T,使得 \forall i \in [1,m], S_i 的导出子图连通。输出构造或报告无解。

多测,\sum n, \sum m \le 2 \times 10^3,2 秒,250 MB。

:::::success[题解]

对集合 S_i,若 S_i 在 T 上连通,则 S_i 的导出子图必然是一棵树,恰有 |S_i|-1 条边。若导出子图分裂成森林,则边数严格小于 |S_i|-1。

设所有 S_i 导出子图的边数和为 f(T),则 f(T) \le \sum \limits_{i=1}^m (|S_i|-1),当且仅当所有集合均连通时等号成立。

另一方面,记 A_u=\{i \mid u \in S_i\},枚举树边 (u,v),则 (u,v) 对 f(T) 的贡献为 |A_u \cap A_v|。只要最大化 \sum\limits_{(u,v)} |A_u \cap A_v| 并判定这个值是否取等,即可得到构造。

取完全图 K_n,将边 (u,v) 的边权设为 |A_u \cap A_v|,求最大生成树即可。A_u 可以使用 bitset 优化,总复杂度 O\left(\dfrac{n^3}{w}\right)。

:::::

:::::info[代码]

const int N = 2005;
int n, m, fa[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
char s[N];
bitset<N> a[N];
struct edge {
    int u, v, w;
    bool operator< (const edge& o) const {return w > o.w;}
} e[N*N];

void _main() {
    cin >> n >> m; iota(fa + 1, fa + n + 1, 1);
    for (int u = 1; u <= n; u++) a[u].reset();
    int sum = 0, mst = 0;
    for (int i = 1; i <= m; i++) {
        cin >> (s + 1);
        for (int u = 1; u <= n; u++) if (s[u] == '1') a[u][i] = 1;
        sum += count(s + 1, s + n + 1, '1') - 1;
    }
    int tot = 0;
    for (int u = 1; u <= n; u++) for (int v = 1; v < u; v++) 
        e[++tot] = {u, v, (a[u] & a[v]).count()};
    sort(e + 1, e + tot + 1);
    vector<edge> T;
    for (int i = 1; i <= tot; i++) {
        int u = find(e[i].u), v = find(e[i].v), w = e[i].w;
        if (u == v) continue;
        fa[u] = v, mst += w, T.emplace_back(e[i]);
    }
    if (mst != sum) return cout << "NO\n", void();
    cout << "YES\n";
    for (auto [u, v, w] : T) cout << u << ' ' << v << '\n';
}

:::::