生成树题型整理

生成树本身的理论见 生成树理论。本文整理如何把题目中的条件转化为生成树，以及转化以后应该调用生成树理论中的哪一部分。

一、连通问题 & 生成树

P1195：不一定要连成一棵树

问题

P1195 口袋的天空
给定 $N$ 个点和 $M$ 条可选带权边，需要选择一些边，使所有点最终恰好形成 $K$ 个连通块，并让所选边权之和最小；如果无法形成恰好 $K$ 个连通块，则输出 No Answer。

数据规模：$1\le N\le 10^3$，$1\le M\le 10^4$，$1\le K\le 10$，$0\le L<10^4$。

最后保留 $k$ 个连通块，那么就不用一直合并到最后只剩一棵树。

一开始有 $n$ 个连通块，每成功加入一条跨块边，连通块数量减少 $1$。

因此从 $n$ 个连通块变成 $k$ 个，只需要进行 $n-k$ 次成功合并。

在 Kruskal 的基础上延伸即可。

二、代价不全是边

P1550：打井

问题

P1550 [USACO08OCT] Watering Hole G
有 $n$ 块田。第 $i$ 块田可以花 $W_i$ 自己打一口井，也可以花 $P_{i,j}$ 修水道连接田 $i,j$。要求最终每块田都能直接拥有水井，或经水道连到某块有井的田，求最小总花费。

数据规模：$1\le n\le 300$，$1\le W_i\le 10^5$，$0\le P_{i,j}\le 10^5$。

每块田有两种方式获得水：一种是自己打井，代价为 $w_i$。另一种是和已经有水的田连接，代价为 $c_{i,j}$。

后者可以看作是标准的边，而前者则把代价限制在点上，这个时候处理就有点麻烦了。

不过还是尝试把点权转移到边上，添加虚拟节点 $0$，如果自己修井，就连边 $(0, i, w_{i})$，然后在新图上求 MST 即可。

这种建模一般称为：虚拟源点。

虚拟源点

虚拟节点本身并不对应题目中的真实对象，它只是用来表示一种所有点都可以独立选择的“外部状态”。如果点 $i$ 可以花费 $c_i$ 独立获得这个状态，就连一条 $(0,i,c_i)$；原来点与点之间的连接仍然保留为普通边。

这样原本“自己获得状态”和“通过其他点获得状态”两种不同的决策，就都被统一成了选边问题，最后只需要让虚拟节点 $0$ 与所有原图节点连通即可。

相似的题目还有 P1194 买礼物 | CF1245D Shichikuji and Power Grid，由于做法类似，此处不再赘述。

三、瓶颈路问题

P1396：先认识 minimax

问题

P1396 营救
给定一张带权无向图，边权表示道路拥挤度。要求从指定起点 $s$ 到终点 $t$ 选择一条路径，使路径上经过道路的最大拥挤度尽可能小，并输出这个最小可能值。题目保证 $s$ 可以到达 $t$。

数据规模：$1\le n\le 10^4$，$1\le m\le 2\times 10^4$，$w\le 10^4$。

如果只问一组 $s,t$：找一条路径，使路径上的最大边权尽可能小。

那么答案等价于：最小的 $W$，使只保留权值不超过 $W$ 的边以后，$s,t$ 已经连通。

因此根据 生成树理论 中提到的，这题有很多种做法：

1. 二分阈值 + 判连通；
2. 按边权从小到大做 Kruskal，直到 $s,t$ 第一次连通；
3. 先建 MST，再查询树上 $s\to t$ 路径最大值。

P2245：多次瓶颈询问

问题

P2245 星际导航
给定一张带权无向图，边权表示航行危险程度。对 $Q$ 组询问 $(A,B)$，要求求出从 $A$ 到 $B$ 的所有路径中，“路径最大边权”的最小可能值；若两点不可达，则输出 impossible。

数据规模：$N\le 10^5$，$M\le 3\times 10^5$，$Q\le 10^5$，边权 $L\le 10^9$；可能存在重边和自环。

本题与上题的区别在于：询问会有很多组 $u,v$。

此时，每次重新跑 Kruskal 显然不合适，根据 MST 的瓶颈性质：任意 MST 上 $u\to v$ 路径的最大边权，就是原图中的 minimax 值。

所以可以直接对原图构造最小生成森林（本题不一定连通）；在森林上做 LCA / 倍增；查询路径最大边权。

注：当然本题也可以使用 KRT 来实现，答案取决于 LCA 的节点权值。

▶

P2245

struct DSU { /* 模板代码略 */ } dsu;

struct Kruskal {
    int u, v; ll w;
    bool operator < ( const Kruskal &oth ) const { return w < oth.w; }
};
vector<Kruskal> edge;

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

int up[maxn][maxlg], dep[maxn];
ll mx1[maxn][maxlg];

void dfs( int u, int p, ll w ) {
    dep[u] = dep[p] + 1, up[u][0] = p;
    mx1[u][0] = w;
    for( int i = 1; i < maxlg; ++ i ) {
        int mid = up[u][i-1];
        up[u][i] = up[mid][i-1];
        mx1[u][i] = max( mx1[u][i-1], mx1[mid][i-1] );
    }
    for( auto [v, nw] : adj[u] ) {
        if( v == p )  continue;
        dfs( v, u, nw );
    }
}

ll ask( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    int diff = dep[u] - dep[v];
    ll mx = -inf;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( ( diff >> i ) & 1 ) {
            mx = max( mx, mx1[u][i] );
            u = up[u][i];
        }
    }
    if( u == v ) return mx;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( up[u][i] == up[v][i] ) continue;
        mx = max({ mx, mx1[u][i], mx1[v][i] });
        u = up[u][i], v = up[v][i];
    }
    mx = max({ mx, mx1[u][0], mx1[v][0] });
    return mx;
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        edge.push_back({ u, v, w });
    }
    
    sort( edge.begin( ), edge.end( ) );
    dsu.init( n );
    for( auto [u, v, w] : edge ) {
        if( dsu.merge( u, v ) ) {
            adj[u].push_back({ v, w });
            adj[v].push_back({ u, w });
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        if( dsu.find( i ) == i ) dfs( i, 0, 0 );
    }

    int q = read( );
    for( int i = 1; i <= q; ++ i ) {
        int u = read( ), v = read( );
        if( u == v ) cout << 0 << '\n';
        else if( !dsu.same( u, v ) ) cout << "impossible" << '\n';
        else cout << ask( u, v ) << '\n';
    }
}

P1967：maximin 的镜像

问题

P1967 [NOIP 2013 提高组] 货车运输
给定一张带权无向图，每条道路的边权表示限重。对多组询问 $(x,y)$，求一辆货车从 $x$ 到 $y$ 时能够运输的最大重量，也就是在所有 $x\to y$ 路径中最大化路径上的最小边权；若两点不可达，输出 $-1$。

数据规模：$n<10^4$，$m<5\times 10^4$，$q<3\times 10^4$，$0\le z\le 10^5$。

本题要求：最大化路径上的最小边权，那么把 Kruskal 顺序反过来即可。

构造最大生成森林后：树上 $u\to v$ 路径的最小边权，就是原图中的 maximin 值。

▶

P1967

struct DSU { /* 模板代码略 */ } dsu;

struct Kruskal { 
    int u, v; ll w; 
    bool operator < ( const Kruskal &oth ) const { return w > oth.w; }
};
vector<Kruskal> edges;

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

int up[maxn][maxlg], dep[maxn];
ll mn1[maxn][maxlg];

void dfs( int u, int p, ll w ) {
    up[u][0] = p, dep[u] = dep[p] + 1;
    mn1[u][0] = w;
    for( int i = 1; i < maxlg; ++ i ) {
        int mid = up[u][i-1];
        up[u][i] = up[mid][i-1];
        mn1[u][i] = min( mn1[u][i-1], mn1[mid][i-1] );
    }
    for( auto [v, nw] : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u, nw );
    }
}

int get_lca( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    int diff = dep[u] - dep[v];
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( ( diff >> i ) & 1 ) u = up[u][i];
    }
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( up[u][i] == up[v][i] ) continue;
        u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}

ll get_min( int u, int anc ) {
    ll mn = inf;
    int diff = dep[u] - dep[anc];
    for( int i = 0; i < maxlg; ++ i ) {
        if( ( diff >> i ) & 1 ) {
            mn = min( mn, mn1[u][i] );
            u = up[u][i];
        }
    }
    return mn;
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ), w = read( );
        edges.push_back({ u, v, w });
    }
    sort( edges.begin( ), edges.end( ) );
    dsu.init( n );

    for( auto [u, v, w] : edges ) {
        if( dsu.merge( u, v ) ) {
            adj[u].push_back({ v, w });
            adj[v].push_back({ u, w });
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        if( dsu.find( i ) == i ) dfs( i, 0, inf );
    }

    int q = read( );
    for( int i = 1; i <= q; ++ i ) {
        int u = read( ), v = read( );
        if( !dsu.same( u, v ) ) {
            cout << -1 << '\n';
            continue;
        }
        int lca = get_lca( u, v );
        ll res = min( get_min( u, lca ), get_min( v, lca ) );
        cout << res << '\n';
    }
}

四、MST 已经求出来了，然后呢？

前面 P2245 是先建出一棵 MST，再利用树上的路径信息回答询问。

如果题目继续要求“某条边必须选”“换一条边以后最优值是多少”，那就不能只停在 MST 本身了，而要开始考虑 基本环与换边。

CF609E：强制某条边进入生成树

问题

CF609E Minimum spanning tree for each edge - 洛谷
给定一张连通带权无向图。对于每一条输入边 $e_i$，分别要求：在所有“必须包含 $e_i$”的生成树中，求最小可能的总边权，并按输入顺序输出每条边对应的答案。

数据规模：$1\le n,m\le 2\times 10^5$，$n-1\le m$，$1\le w_i\le 10^9$；原图连通，无自环和重边。

本题可以看作在 P2245 的基础上再往前走一步：MST 已经建出来了，现在要求某条边 $e=(u,v,w)$ 必须被选。

如果 $e$ 本来就在 MST 中，那么答案自然还是原 MST 的权值 $S$。

否则把 $e$ 加入 MST，就会形成一个基本环。既然 $e$ 已经必须保留，那么为了让新的生成树尽可能小，就应该删掉原来 $u\to v$ 路径上的最大边。

记路径最大边权为 $M(u,v)$，答案就是：$S+w-M(u,v)$。

不过实际上不需要特判 $e$ 是否为树边。如果 $e$ 本来就在 MST 中，那么 $u,v$ 在 MST 上的路径就是这条边本身，因此 $M(u,v)=w$，同一个公式仍然会得到 $S$。

实现上其实就是 P2245 的 MST + LCA 路径最大值，只不过原来是在查询瓶颈，现在是在计算一次换边后的新权值。

▶

CF609E

struct DSU { /* 模板代码略 */ } dsu;

struct Kruskal { 
    int u, v, w, id; 
    bool operator < ( const Kruskal &oth ) const { return w < oth.w; }
};
vector<Kruskal> edges;

struct Edge { int v; ll w; };
vector<Edge> adj[maxn];

ll mst;

int up[maxn][maxlg], dep[maxn];
ll mxw[maxn][maxlg];

void dfs( int u, int p, ll w ) {
    up[u][0] = p, dep[u] = dep[p] + 1;
    mxw[u][0] = w;
    for( int i = 1; i < maxlg; ++ i ) {
        int mid = up[u][i-1];
        up[u][i] = up[mid][i-1];
        mxw[u][i] = max( mxw[u][i-1], mxw[mid][i-1] );
    }
    for( auto [v, w] : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u, w );
    }
}

ll ask( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    ll res = 0;
    int diff = dep[u] - dep[v];
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( ( diff >> i ) & 1 ) {
            res = max( res, mxw[u][i] );
            u = up[u][i];
        }
    }
    if( u == v ) return res;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( up[u][i] == up[v][i] ) continue;
        res = max({ res, mxw[u][i], mxw[v][i] });
        u = up[u][i], v = up[v][i];
    }
    res = max({ res, mxw[u][0], mxw[v][0] });
    return res;
}

void solve( ) {
    int n = read( ), m = read( );
    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ), w = read( );
        edges.push_back({ u, v, w, i });
    }
    vector<Kruskal> ori_edges = edges;
    sort( edges.begin( ), edges.end( ) );
    dsu.init( n );
    for( auto [u, v, w, id] : edges ) {
        if( dsu.merge( u, v ) ) {
            mst += w;
            adj[u].push_back({ v, w });
            adj[v].push_back({ u, w });
        }
    }
    dfs( 1, 0, 0 );
    for( auto [u, v, w, id] : ori_edges ) {
        cout << mst + w - ask( u ,v ) << '\n';
    }
}

P4180：严格次小生成树

问题

P4180 [BJWC2010] 严格次小生成树
给定一张带权无向图，先定义最小生成树权值为 $S$。要求在所有生成树中，找出总边权 严格大于 $S$ 的最小值，即严格次小生成树的权值。题目保证严格次小生成树存在。

数据规模：$N\le 10^5$，$M\le 3\times 10^5$，边权属于 $[0,10^9]$；可能存在自环。

和上题其实还是同一个换边动作，区别在于：CF609E 已经指定了要加入哪条边，而本题需要枚举所有非树边，找一次 增量最小且严格大于 $0$ 的换边。

对于一条非树边 $e=(u,v,w)$，加入后形成基本环。如果树上 $u\to v$ 路径的最大边权 $mx_1<w$，那直接删掉 $mx_1$ 即可。

但如果 $mx_1=w$，删掉它只会得到另一棵同权 MST，不满足“严格次小”。这个时候就要继续找路径上 严格小于 $w$ 的最大边权，也就是维护不同权值意义下的严格次大值 $mx_2$。

由于当前这棵树本身就是 MST，根据基本环上的交换条件一定有 $mx_1\le w$，所以实现时只需要讨论 $mx_1<w$ 和 $mx_1=w$ 两种情况，并不存在 $mx_1>w$ 的情况。

因此本题相较于普通的路径最大值查询，多了一层同时维护路径上的最大值和严格次大值。

▶

P4180

struct DSU { /* 模板代码略 */ } dsu;

struct Edge {
    int u, v; ll w; bool used;
    bool operator < ( const Edge &oth ) const { return w < oth.w; }
};
vector<Edge> edge;

struct Node { int v; ll w; };
vector<Node> adj[maxn];

int up[maxn][maxlg];
ll mx1[maxn][maxlg];
ll mx2[maxn][maxlg];

int dep[maxn];
ll mst;

void addval( ll &m1, ll &m2, ll x ) {
    if( x == -1 ) return;
    if( m1 < x ) m2 = m1, m1 = x;
    else if( m2 < x && x < m1 ) m2 = x; 
}

void updval( ll &m1, ll &m2, ll v1, ll v2 ) {
    addval( m1, m2, v1 );
    addval( m1, m2, v2 );
}

void dfs( int u, int p, ll w ) {
    dep[u] = dep[p] + 1, up[u][0] = p;
    mx1[u][0] = w, mx2[u][0] = -1;
    for( int i = 1; i < maxlg; ++ i ) {
        int mid = up[u][i-1];
        up[u][i] = up[mid][i - 1];
        mx1[u][i] = mx1[u][i - 1];
        mx2[u][i] = mx2[u][i - 1];
        updval( mx1[u][i], mx2[u][i], mx1[mid][i-1], mx2[mid][i-1] );
    }
    for( auto [v, nw] : adj[u] ) {
        if( v == p ) continue;
        dfs( v, u, nw );
    }
}

int get_lca( int u, int v ) {
    if( dep[u] < dep[v] ) swap( u, v );
    int diff = dep[u] - dep[v];
    for( int i = 0; i < maxlg; ++ i ) {
        if( ( diff >> i ) & 1 ) u = up[u][i];
    }
    if( u == v ) return u;
    for( int i = maxlg - 1; i >= 0; -- i ) {
        if( up[u][i] == up[v][i] ) continue;
        u = up[u][i], v = up[v][i];
    }
    return up[u][0];
}

pair< ll, ll > query( int u, int anc ) {
    ll res1 = -1, res2 = -1;
    int diff = dep[u] - dep[anc];
    for( int i = 0; i < maxlg; ++ i ) {
        if( ( diff >> i ) & 1 ) {
            updval( res1, res2, mx1[u][i], mx2[u][i] );
            u = up[u][i];
        }
    }   
    return { res1, res2 };
}

void solve( ) {
    int n = read( ), m = read( );

    memset( mx1, -1, sizeof( mx1 ) );
    memset( mx2, -1, sizeof( mx2 ) );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        edge.push_back({ u, v, w, 0 });
    }
    sort( edge.begin( ), edge.end( ) );

    dsu.init( n );
    int cnt = 0;
    mst = 0;

    for( int i = 0; i < m; ++ i ) {
        auto &[u, v, w, used] = edge[i];
        if( dsu.merge( u, v ) ) {
            mst += w;
            used = 1;
            cnt ++;
            adj[u].push_back({ v, w });
            adj[v].push_back({ u, w });
            if( cnt == n - 1 ) break;
        }
    }

    if( cnt != n - 1 ) {
        cout << -1 << '\n';
        return;
    }

    dep[0] = 0;
    dfs( 1, 0, -1 );

    ll del = inf;
    for( auto &[u, v, w, used] : edge ) {
        if( used || u == v ) continue;
        int lca = get_lca( u, v );
        auto [x1, x2] = query( u, lca );
        auto [y1, y2] = query( v, lca );
        updval( x1, x2, y1, y2 );
        ll remove = -1;
        if( x1 < w ) remove = x1;
        else if( x1 == w ) remove = x2;
        if( remove != -1 ) del = min( del, w - remove );
    }
    printf( "%lld\n", mst + del );
}

五、生成树里必须恰好选 $k$ 条某类边

前面的题都只关心“哪些边更便宜”，但有些题还会额外限制：某一类边必须刚好选 $k$ 条。

这种限制第一次遇到时，先不要急着往 WQS 上套。最基础的问题其实是：到底能不能凑出恰好 $k$ 条？

P3623：先把数量凑出来

问题

P3623 [APIO2008] 免费道路
给定 $N$ 个村庄和 $M$ 条道路，每条道路分为鹅卵石路和水泥路两类。需要从原图中选出尽可能少且能让任意两村之间存在唯一免费路径的一组道路，也就是选出一棵生成树，并要求其中 恰好有 $K$ 条鹅卵石路。若存在方案则任意输出一棵，否则输出 no solution。

数据规模：$1\le N\le 2\times 10^4$，$1\le M\le 10^5$，$0\le K\le N-1$；任意一对村庄之间至多有一条道路。

这题没有边权，难点就只有一个：如何保证最后的生成树里刚好有 $k$ 条鹅卵石路？

先反过来想：最少需要多少条鹅卵石路？

如果先把所有水泥路都尽可能连起来，那么最后会剩下若干个水泥路连通块。这些连通块之间想要继续合并，只能使用鹅卵石路。

因此重新扫描鹅卵石路，把能够连接两个不同连通块的边先记下来。这一批边就是当前构造下“为了连通不得不补”的鹅卵石骨架。

如果这时候已经用了超过 $k$ 条鹅卵石路，那显然无解。

否则重新建立 DSU，先加入这批骨架，再继续加入其他不会成环的鹅卵石路，直到数量补到 $k$，最后再用水泥路把整棵树补完即可。

如果记只保留水泥路时有 $c_1$ 个连通块，那么最少需要 $K_{\min}=c_1-1$ 条鹅卵石路。同理，只保留鹅卵石路时若有 $c_0$ 个连通块，那么鹅卵石路最多只能在森林中贡献 $K_{\max}=n-c_0$ 条。

在整张图本身连通的前提下，可行数量就在 $[K_{\min},K_{\max}]$ 之间。

不过实现时其实不需要专门把 $K_{\max}$ 算出来。第二轮继续加入不会成环的鹅卵石路，如果最后仍然补不到 $k$ 条，就等价于发现 $k>K_{\max}$，直接判无解即可。

注：第一轮找出的“必要边”只是当前构造选出的一组最低需求骨架，并不是说这些具体的边在所有合法生成树中都必须出现。

▶

P3623

struct DSU { /* 模板代码略 */ } dsu;

struct Edge { int u, v, c; bool need; };
vector<Edge> edge0, edge1, ans;

void fail( ) {
    cout << "no solution" << '\n';
    return ;
}

void solve( ) {
    int n = read( ), m = read( ), k = read( );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( ), c = read( );
        if( c == 0 ) edge0.push_back({ u, v, c, 0 });
        else edge1.push_back({ u, v, c, 0 });
    }

    dsu.init( n );
    int tot = 0, mn = 0;

    for( auto [u, v, c, need] : edge1 ) {
        if( dsu.merge( u, v ) ) tot ++;
    }

    for( auto &[u, v, c, need] : edge0 ) {
        if( dsu.merge( u, v ) ) {
            need = true;
            mn ++, tot ++;
        }
    }

    if( tot != n - 1 || mn > k ) return fail( );

    dsu.init( n );
    int cnt = 0;

    for( auto [u, v, c, need] : edge0 ) {
        if( !need ) continue;
        if( dsu.merge( u, v ) ) {
            cnt ++;
            ans.push_back({ u, v, c, need });
        }
    }
    
    for( auto [u, v, c, need] : edge0 ) {
        if( cnt == k ) break;
        if( need ) continue;
        if( dsu.merge( u, v ) ) {
            cnt ++;
            ans.push_back({ u, v, c, need });
        }
    }
    if( cnt != k ) return fail( );

    for( auto [u, v, c, need] : edge1 ) {
        if( dsu.merge( u, v ) ) {
            ans.push_back({ u, v, c, need });
        }
    }
    if( ans.size( ) != n - 1 ) return fail( );

    for( auto [u, v, c, need] : ans ) {
        cout << u << ' ' << v << ' ' << c << '\n';
    }
}

P2619：不仅要恰好 $k$ 条，还要最小

问题

P2619 [国家集训队] Tree I
给定一张连通带权无向图，每条边为黑色或白色。要求选择一棵生成树，使其中 恰好有 need 条白边，并在满足数量限制的所有生成树中最小化原边权总和。题目保证有解。

数据规模：$V\le 5\times 10^4$，$E\le 10^5$，边权属于 $[1,100]$；顶点从 $0$ 开始编号。

本题与上题的区别在于：不只是要凑出 need 条白边，还要在所有满足数量限制的生成树中继续最小化总边权。

这个时候就不能像 P3623 一样随便补边了。

回顾 Kruskal 生成树的做法，将所有边从小到大排序，然后逐一加入到图中。所以为了限制白边的数量，我们尝试修改白边在排序后的 edges 里出现的位置。

也就是说，我们可以给所有白边统一增加一个额外代价 $x$：$w'_e=w_e+x$，然后按照修改后的边权重新跑 Kruskal。

当 $x$ 越大时，白边整体越贵。在同权时固定优先选择白边以后，Kruskal 得到的白边数量会随 $x$ 增大而单调不增。于是可以二分这个额外代价，找到白边数量跨过 need 的临界位置。

假设修改后 MST 的权值为 $S'$，最终需要恰好 need 条白边，那么把额外加进去的代价减掉即可：$S'-need\cdot x$。

注：本题还有实现细节，修改后的边权可能相同，而不同 MST 使用的白边数量不一定相同，所以在同边权时要优先选择白边。

这就是生成树上的 WQS 二分。

▶

P2619

struct DSU { /* 模板代码略 */ } dsu;

struct Edge { int u, v, col; ll w; };
vector<Edge> edge;
int n, m, need;
ll mst;

bool cmp( const Edge &a, const Edge &b ) {
    if( a.w != b.w ) return a.w < b.w;
    return a.col < b.col;
}

int kruskal( int N ) {
    dsu.init( N );
    sort( edge.begin( ), edge.end( ), cmp );
    mst = 0;
    int white = 0;
    int cnt = 0; // 已选边数
    for( auto [u, v, col, w] : edge ) {
        if( dsu.merge( u, v ) ) {
            mst += w;
            ++ cnt;
            if( col == 0 ) ++ white;
            if( cnt == N - 1 ) break;
        }
    }
    return white;
}

bool check( int mid ) {
    for( int i = 0; i < m; ++ i ) {
        if( edge[i].col == 0 ) edge[i].w += mid;
    }
    bool ok = ( kruskal( n ) >= need );
    for( int i = 0; i < m; ++ i ) {
        if( edge[i].col == 0 ) edge[i].w -= mid;
    }
    return ok;
}

void solve( ) {
    n = read( ), m = read( ), need = read( );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ) + 1, v = read( ) + 1;
        int w = read( ), c = read( );
        edge.push_back({ u, v, c, w });
    }

    int l = -101, r = 101, ans = 0;
    while( l <= r ) {
        int mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    check( ans );
    cout << mst - need * ans << '\n';
}

P5633：限制一个点的度数

问题

P5633 最小度限制生成树
给定一张带权无向图和指定顶点 $s$，要求找一棵总边权最小的生成树，同时满足 $s$ 在这棵生成树中的度数 恰好为 $k$。如果不存在满足条件的生成树，则输出 Impossible。

数据规模：$n\le 5\times 10^4$，$m\le 5\times 10^5$，$1\le k\le 100$，$0\le w\le 3\times 10^4$。

这题与上题非常像，区别只在于：前面“特殊边”是由颜色定义的，而这里把所有与 $s$ 相连的边看成特殊边即可。

生成树中 $s$ 的度数恰好为 $k$，也就等价于：恰好选择 $k$ 条与 $s$ 相连的边。

不过在二分以前还要先判断这个度数是否可行。

先完全不使用与 $s$ 相连的边，只用其他边尽可能合并。设此时还剩 block 个连通块，那么至少需要 block-1 条与 $s$ 相连的边才能把这些部分接起来，因此这给出了 $s$ 度数的下界。

反过来，只使用与 $s$ 相连的边做森林，最多能够成功加入多少条，就给出了度数上界。先判断 $k$ 是否落在这个可行区间里，再进入后面的 WQS 二分。

因此仍然可以给这些边统一增加参数 $\Delta$。$\Delta$ 越大，这类边越贵，MST 中选择的数量就越少，再二分参数即可。

实现时还可以把 “与 $s$ 相连” 和 “不与 $s$ 相连” 的边分别排序，每次 check 时按修改后的边权归并，这样就不用每次重新排序全部边。

▶

P5633

struct DSU { /* 模板代码略 */ } dsu;

struct Edge { int u, v; ll w; int need; };
vector<Edge> edgeA, edgeB;

bool cmp( Edge A, Edge B ) {
    if( A.w != B.w ) return A.w < B.w;
    return A.need > B.need;
}

ll mst;
int cnt;
int n, m, s, k;

vector<Edge> merge_sort( ll delta ) {
    int cnta = edgeA.size( ), cntb = edgeB.size( );
    vector<Edge> res;
    res.reserve( cnta + cntb );
    for( int i = 0; i < cnta; ++ i ) edgeA[i].w += delta;
    int a = 0, b = 0;
    while( a < cnta && b < cntb ) {
        if( cmp( edgeA[a], edgeB[b] ) ) res.push_back( edgeA[a ++] );
        else res.push_back( edgeB[b ++] );
    }
    while( a < cnta ) res.push_back( edgeA[a ++] );
    while( b < cntb ) res.push_back( edgeB[b ++] );
    for( int i = 0; i < cnta; ++ i ) edgeA[i].w -= delta;
    return res;
}

bool check( ll delta ) {
    auto edges = merge_sort( delta );
    dsu.init( n );
    mst = cnt = 0;
    for( auto [u, v, w, need] : edges ) {
        if( !dsu.merge( u, v ) ) continue;
        mst += w, cnt += need;
    }
    return cnt >= k;
}

void fail( ) {
    cout << "Impossible" << '\n';
    return;
}

void solve( ) {
    n = read( ), m = read( );
    s = read( ), k = read( );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        ll w = read( );
        if( u == s || v == s ) edgeA.push_back({ u, v, w, 1 });
        else edgeB.push_back({ u, v, w, 0 });
    }

    sort( edgeA.begin( ), edgeA.end( ), cmp );
    sort( edgeB.begin( ), edgeB.end( ), cmp );

    dsu.init( n );
    int block = n;
    for( auto [u, v, w, need] : edgeB ) {
        if( dsu.merge( u, v ) ) block --;
    }

    int mn = block - 1;
    for( auto [u, v, w, need] : edgeA ) {
        if( dsu.merge( u, v ) ) block --;
    }
    if( block != 1 ) return fail( );

    dsu.init( n );
    int mx = 0;
    for( auto [u, v, w, need] : edgeA ) {
        if( dsu.merge( u, v ) ) mx ++;
    }
    if( k < mn || mx < k ) return fail( );

    ll l = -inf, r = inf, ans = inf;
    while( l <= r ) {
        ll mid = ( l + r ) >> 1;
        if( check( mid ) ) ans = mid, l = mid + 1;
        else r = mid -1;
    }

    check( ans );
    cout << mst - 1ll * k * ans << '\n';
}

六、边太多，根本建不出来

如果题目直接给一张完全图，而 $n$ 又到了 $10^5$ 量级，那么显然不可能真的枚举 $\Theta(n^2)$ 条边。这个时候的问题就是 边没有办法先建出来 了。

CCPC 2025 Online C：造桥与砍树

问题

CCPC 2025 Online C 造桥与砍树
有 $n$ 座互不连通的岛，初始只能到达 $1$ 号岛。需要连续 $n-1$ 天建桥，每天建一条连接两个岛的桥，并要求这条桥至少有一个端点当前已经可达；最终所有岛都要可达。第 $i$ 个岛每天会刷新为 $t_i$ 棵树，某天若建桥连接 $u,v$，就会砍掉两岛当天的全部树，得到 $t_u+t_v$ 根圆木；每 $k$ 根圆木可以合成硬木，当天未被合成的圆木会被清空。要求安排整个建桥顺序，使 $n-1$ 天中被清空的圆木总数最小。

数据规模：多组数据；$1\le n\le 10^5$，$1\le k\le 10^9$，$0\le t_i\le 10^9$，所有测试的 $\sum n\le 2\times 10^5$。

这题其实很好建模：任意两个点 $u,v$ 之间连边，边权为 $(t_u+t_v)\bmod k$，问题就是在这张完全图上求 MST。记 $a_i=t_i\bmod k$，那么边权也可以写成 $(a_u+a_v)\bmod k$。

真正的难点在于 $n=10^5$，显然不能把 $\Theta(n^2)$ 条边全部建出来。这时就没法直接用 Kruskal，考虑换成 Borůvka：只要每一轮能找到每个当前连通块的最轻出边就行。

对于固定的 $u$，要让 $(a_u+a_v)\bmod k$ 尽可能小，那只需要在有序集合里寻找第一个满足 $a_v\ge k-a_u$ 的点；如果不存在，就从最小值重新绕回来，这一步可以通过二分来优化。

因此每一轮可以暂时把当前连通块里的点从全局集合中拿掉，再对块内每个点查询最优的块外点，取其中最小的一条作为这个连通块的最轻出边，最后再把点放回去并统一合并。

所以本题启示我们，在这种隐式完全图上，如果能快速查询每个连通块的最轻出边，可以考虑使用 Borůvka 来实现。

▶

CCPC 2025 Online C

struct DSU { /* 模板代码略 */ } dsu;

struct Edge { int u, v; ll w; };
ll a[maxn];

void solve( ) {
    int n = read( );
    ll k = read( );
    for( int i = 1; i <= n; ++ i ) {
        a[i] = read( ) % k;
    }

    set< pair<ll, int> > st;
    for( int i = 2; i <= n; ++ i ) {
        st.insert({ a[i], i });
    }

    int cnt = n; // 连通块数量
    ll ans = 0;

    dsu.init( n );
    while( cnt > 1 ) {

        vector< vector<int> > tmp(n + 1);

        for( int i = 1; i <= n; ++ i ) {
            tmp[dsu.find(i)].push_back( i );
        }

        vector<Edge> best( n + 1, { 0, 0, inf } );

        for( int rt = 1; rt <= n; ++ rt ) {
            if( tmp[rt].empty( ) ) continue;
            for( int u : tmp[rt] ) {
                st.erase({ a[u], u });
            }

            if( !st.empty( ) ) {
                for( int u : tmp[rt] ) {

                    auto it = st.lower_bound({ k - a[u], -1 });
                    if( it == st.end( ) ) it = st.begin( );
                    ll cost = ( a[u] + it->first ) % k;
                    if( cost < best[rt].w ) {
                        best[rt] = { u, it->second, cost };
                    }
                }
            }
            for( int u : tmp[rt] ) {
                st.insert({ a[u], u });
            }
        }
        for( int rt = 1; rt <= n; ++ rt ) {
            if( best[rt].w == inf ) continue;
            if( dsu.merge(best[rt].u, best[rt].v) ) {
                ans += best[rt].w;
                --cnt;
            }
        }
    }

    cout << ans << '\n';
}

ABC469F：另一种完全图

问题

ABC469F GCD Maximum Spanning Tree
给定严格递增的正整数序列 $A_1,\dots,A_N$。建立一张 $N$ 个点的完全无向图，点 $i,j$ 之间的边权为 $\gcd(A_i,A_j)$。要求求出这张完全图的 最大生成树 权值和。

数据规模：$2\le N\le 2\times 10^5$，$1\le A_1<A_2<\cdots<A_N\le 10^6$。

最自然的思路就是建图，然后跑一遍 Kruskal 最大生成树，从大到小处理边权即可。但是发现点数太多了，我们没法直接构建完全图，更何况每个点对算 $\gcd$ 的开销呢？

于是发现，其实很多边是根本用不上的；对于一个整数 $d$，所有值为 $d$ 的倍数的点之间，都存在权值至少为 $d$ 的边。

所以我们从最大值开始倒序枚举 $d$，然后收集所有 $d$ 的倍数在序列中对应的点，尝试用并查集合并，当然我们不需要把树完整建出来，所以每次合并，相当于选择了一条当前权值为 $d$ 的边，统计答案即可。

由于枚举到 $d$ 时，所有权值大于 $d$ 的边都已经处理完毕。若两个当前不连通的点的 $gcd$ 大于 $d$，那么它在枚举到该 $gcd$ 时就已经被合并了，所以每次成功的合并都可以看作选择了一条权值为 $d$ 的边。

所以这题更接近隐式 Kruskal，并不需要显式把所有的边都建出来。

这里枚举所有 $d$ 的倍数，总访问次数为 $\displaystyle \sum_{d=1}^{V}\left\lfloor\frac{V}{d}\right\rfloor=\mathcal O(V\log V)$，其中 $V=\max A_i\le 10^6$，所以这种枚举方式可以通过。

▶

ABC469F

struct DSU { /* 模板代码略 */ } dsu;

int a[maxn];
int pos[maxv];

void solve( ) {
    int n = read( );
    int mx = -1;
    for( int i = 1; i <= n; ++ i ) {
        int x = read( );
        pos[x] = i;
        mx = max( mx, x );
    }

    dsu.init( n );
    
    ll ans = 0;
    for( int d = mx; d >= 1; -- d ) {
        int cur = 0;
        for( int val = d; val <= mx; val += d ) {
            int nxt = pos[val];
            if( !nxt ) continue;
            if( !cur ) cur = nxt;
            else if( dsu.merge( cur, nxt ) ) {
                ans += d;
            }
        }
    }
    cout << ans << '\n';
}

对比

• CCPC Online C：能快速找每个连通块的最轻出边，所以用 Borůvka；
• ABC469F：能直接恢复权值阈值下的连通块变化，所以沿 Kruskal 做。

二者共同说明了一点：完全图的边不一定真的要建出来，真正要找的是足够完成安全合并的信息。

七、小结

摘要

最基础的连通最优化直接落到 MST；
点上的独立激活代价可以通过虚拟节点统一成边；
瓶颈路问题可以借助 MST / MaxST 的瓶颈性质；
固定 MST 后的强制选边、次小生成树则来自基本环交换。

如果继续限制某类边必须选择 $k$ 条，需要先区分可行性与带权最优化：
前者研究特殊边数量的可行区间，后者可以进一步进入参数化 MST / WQS 二分。

若是完全图无法建立，则需要回到算法真正需要的信息：
能否快速查询每个连通块的最轻出边，或者直接恢复权值阈值下的连通块合并过程。

关联

• 理论基础见 生成树理论。
• 树上路径查询见 LCA 体系。
• 图论导航见 20_图论。