题解：P15455 [JOI 2026 SemiFinal] 新的桥梁 / New Bridge

chen_zhe · 2026-02-26 20:14:58 · 题解

这是由 AI 翻译为中文文本的官方题解

子任务 1

确定首都之后的操作，即为寻找带权无向图的最小生成树的算法，被称为“Prim 算法”。Prim 算法通过使用 priority queue 等数据结构，可以在单次 O(M \log M) 的时间复杂度内执行。将此操作对 N 种首都情况分别进行，计算复杂度为 O(NM \log M)。

子任务 2

由于 Prim 算法是求解最小生成树的算法，如果存在某条边使得有新的顶点变得可达，那么这条边必定包含在最小生成树中。因此，可以忽略不包含在最小生成树中的边。首先求出最小生成树，然后在该图上改变起点为 N 种情况执行 Prim 算法，计算复杂度变为 O(N^2 \log N)。

子任务 3

从 s 出发可达的岛屿集合始终构成一个区间。 考虑 s < i 的情况，当从 s 可以到达 i 时，存在某个 j（j \le s），使得从 j 到 i 的区间都是可达的。这个 j 的值是，设 s 到 i 路径上边的最大权值为 m，从 s 开始向编号较小的方向查看时，第一次出现权值大于 m 的边的位置。固定 i，当 s 的编号逐渐减小时，j 的编号也会同样逐渐减小。因此，利用尺取法（双指针）的要领，可以依次求出 s = i - 1, i - 2, \dots, 1 对应的 j 的值。利用同样的方法也可以计算 s = i + 1, i + 2, \dots, N 的情况，计算复杂度为 O(NQ)。

子任务 4, 5，满分解法

考虑与 Prim 算法齐名的另一种求解最小生成树的算法——Kruskal 算法。

假设在 Kruskal 算法的某一步中，连通分量 A 和连通分量 B 通过连接 A 中顶点 x 和 B 中顶点 y 的边 (x, y) 进行合并。此时，对于属于 A 的顶点 a 和属于 B 的顶点 b，可以确定 D_{a,b} = |A| + D_{y,b}。在这里，对于顶点 b 的不便度 D_{1,b} + D_{2,b} + \dots + D_{N,b} 的表达式，通过反复进行前面等式所表示的代入操作，最终可以将其表示为 |A_1| + |A_2| + \dots 的形式。（请注意 D_{b,b} = 0。）可以发现，在这个表达式中 |A| 出现的次数，等于在边 (x, y) 处切断最小生成树时，位于 x 一侧的顶点总数 k。因此，只需对包含在 B 中的所有顶点 b 的得分统一加上 |A| \times k 即可。同理，对包含在 A 中的所有顶点 a 的得分也要加上 |B| \times (N - k)。

当图是一条路径时，这个加法操作相当于区间加法。因为只需要在最后求出结果即可，所以可以使用 imos 法（差分法）。 对于一般的图，这个加法操作对应于在“表示合并过程的树（Kruskal 重构树）”中，对子树的所有节点进行加法的操作。因为只需要在最后求出结果即可，所以只需将该值记录在子树的根节点上，之后一边将这些值累加，一边自顶向下地向子节点传递即可。

在计算复杂度方面，求解最小生成树时的边排序过程成为了瓶颈，为 O(M \log M)。

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i < (n);i++)
#define eb emplace_back
#define si(x) (ll)x.size()
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define vll vector<ll>
#define inf LLONG_MAX / 3
template<class T> bool chmin(T& a, const T& b){ if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, const T& b){ if(a >= b) return 0; a = b; return 1; }
typedef long long ll;

struct uf{
    vll p;
    void init(ll n){
        p.resize(n);
        rep(i,n)p[i] = i;
    }
    ll par(ll x){
        return p[x] = (x == p[x] ? x : par(p[x]));
    }
    bool same(ll a,ll b){
        a = par(a);
        b = par(b);
        return a == b;
    }
    void unite(ll a,ll b){
        a = par(a);
        b = par(b);
        p[a] = b;
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    ll n,m,q;
    cin>>n>>m>>q;
    vector<tuple<ll,ll,ll> >edges;
    rep(i,m){
        ll a,b,c;
        cin>>a>>b>>c;
        a--,b--;
        edges.eb(c,a,b);
    }
    sort(all(edges));

    vector<pll>tedges;
    vector<vll> t(n);
    vll szt(n);
    auto gawa = [&](ll x,ll y){

        if(szt[x] > szt[y]){
            return n - szt[y];
        }
        return szt[x];
    };
    {
        uf uf;
        uf.init(n);
        for(auto &&[c,a,b] : edges){
            if(uf.same(a,b))continue;
            uf.unite(a,b);
            tedges.eb(a,b);
            t[a].eb(b);
            t[b].eb(a);
        }
        function<ll(ll,ll)> dfs = [&](ll x,ll frm){
            szt[x] = 1;
            for(auto &&y: t[x])if(y != frm){
                szt[x] += dfs(y,x);
            }
            return szt[x];
        };
        dfs(0, -1);
    }

    ll id = n;
    vll ad(n,0),p(n),sz(n, 1);
    vll p_star(n);
    rep(i,n)p[i] = p_star[i] = i;
    function<ll(ll)> par = [&](ll x){
        return p_star[x] = (p_star[x] == x ? x : par(p_star[x]));
    };

    for(auto &&[x,y] : tedges){
        ll a = par(x);
        ll b = par(y);
        ad[b] += sz[a] * gawa(x,y);
        ad[a] += sz[b] * gawa(y,x);
        p[a] = p_star[a] = p[b] = p_star[b] = id;
        p.eb(id);
        p_star.eb(id);
        ad.eb(0);
        sz.eb(sz[a] + sz[b]);
        id++;
    }

    for(int i = id - 1;i >= 0; i--){
        ad[i] += ad[p[i]];
    }

    while(q--){
        ll x;
        cin>>x;
        x--;
        cout<<ad[x]<<"\n";
    }
}