新的桥梁 / New Bridge JOI 2026 SemiFinal

[JOI 2026 SemiFinal] 新的桥梁 / New Bridge

给一个 nn 个点 mm 条边的带权图。

定义 Ds,iD_{s,i} 表示以 ss 作为起点执行 Prim 最小生成树算法，ii 是第几个被扩展到的。

多次询问，每次给定 xx，求 ∑sDs,x\sum\limits_s D_{s,x}。

n≤3×105,m≤6×105n\le 3\times10^5,m\le 6\times 10^5。

所有边边权互不相同。

首先给出一个样例：

1
2
3
4
5
6
4 5
1 3 1
2 3 2
3 4 3
4 2 4
1 4 5

可以先模拟以下，以加深对题解的理解。

由于 Prim 算法求出的最小生成树和 Kruskal 一致，不妨考虑 Kruskal 以及 Kruskal 重构树。

对于 Kruskal 重构树上的一个非叶子节点，其代表一条边，连接两个连通块 S1,S2S_1,S_2，那么所有会先到 S1S_1 的节点必然会至少为 S2S_2 中的每一个节点添加 ∣S1∣|S_1| 的贡献（因为根据 Kurskal 的过程，他必须先把 S1S_1 中的点走完）。同理可的先到 S2S_2 中的点到 S1S_1 必然会产生 ∣S2∣|S_2| 的贡献。

因此我们就有一个基本的算法框架（伪代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def Solve():
    while can_Kruskal():
        EDGE edge=Kruskal_edge()
        def u,v
        [u,v]=edge
        u=getf(u)
        v=getf(v)
        def szu,szv
        [szu,szv]=[get_sz(u),get_sz(v)]
        def totu,totv
        [totu,totv]=[first_to(u),first_to(v)]
        subtree_add(u,totv*szv)
        subtree_add(v,totu*szu)
    while Q--:
        def x;
        x=get_input()
        output(ans[x])
    exit

所以现在的问题就是：如何求出有多少个点会先到 S1,S2S_1,S_2？

不妨先建立最小生成树，然后我们会发现：设连接 S1,S2S_1,S_2 的点分别是 u,vu,v，那么有一个显然的事实：

最小生成树上，vv 那一侧的点作为起点一定先到 S2S_2，uu 那一侧的起点一定先到 S1S_1。

于是先建立最小生成树，然后记录子树大小即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;
const int N=600010;
using ll=long long;
ll ans[N];
int n,m,Q,tot[N],f[N],sz[N],F[N];
struct node{int u,v,w;}q[N];
bool operator<(node x,node y){return x.w<y.w;}
vector<int>v[N];
int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}
void kruskal(){
    for(int i=1;i<=n;i++)f[i]=i;
    sort(q+1,q+1+m);
    for(int i=1;i<=m;i++){
        int x=getf(q[i].u),y=getf(q[i].v);
        if(x!=y){
            f[y]=x;
            v[q[i].u].push_back(q[i].v);
            v[q[i].v].push_back(q[i].u);
        }
    }
}
void dfs(int x,int fa){
    F[x]=fa,tot[x]=1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        tot[x]+=tot[u];
    }
}
void Kruskal(){
    for(int i=1;i<(n<<1);i++)f[i]=i,sz[i]=1,v[i].clear();
    sort(q+1,q+1+m);
    for(int i=1,cnt=n;i<=m&&cnt<(n<<1)-1;i++){
        int x=getf(q[i].u),y=getf(q[i].v);
        if(x!=y){
            ++cnt;
            f[x]=f[y]=cnt;
            sz[cnt]=sz[x]+sz[y];
            v[cnt].push_back(x);
            v[cnt].push_back(y);
            int t1=(F[q[i].u]==q[i].v?tot[q[i].u]:n-tot[q[i].v]);
            int t2=n-t1;
            ans[x]+=1ll*t2*sz[y];
            ans[y]+=1ll*t1*sz[x];
        }
    }
}
void dfs2(int x,int fa){
    for(int u:v[x])if(u!=fa)ans[u]+=ans[x],dfs2(u,x);
}
int main(){
    scanf("%d%d%d",&n,&m,&Q);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
    kruskal();
    dfs(1,0);
    Kruskal();
    dfs2((n<<1)-1,0);
    while(Q--){
        int x;scanf("%d",&x);
        printf("%lld\n",ans[x]);
    }
    return 0;
}