题意

题目链接。

有 $n$​ 行 $m+1$​ 列格点，第 $1$​ 列和第 $2$​ 列格点之间有 $e$ 条边，第 $i$ 条边的边权为 $c_i$，保证联通。第 $i$ 与 $i+1$ 列中的边是由第 $1$ 列和第 $2$ 列的边复制得到的。对于前 $i$ 列（$2 \le i \le m+1$），求对于前 $i$ 列的点与端点都在前 $i$​​ 列的边构成的图，这张图的最小生成树所有边的权值和为多少。

数据范围：$1≤n≤10^5,1≤m≤10^5,1≤e≤10^6,1≤c≤30$​​​。

解析

首先考虑第 $1$ 列和第 $2$ 列之间的边数肯定不少于后面第 $i$ 与第 $i+1$ 列，因为前两列之间的点一定是完全没有联通起来的，而后面各列由于前面已经有很多边了，可能会存在第 $i$ 列有一些边已经被联通起来了。

接着考虑对于第 $i$ 列和第 $i+1$​ 列，这两列之间所连的边一定包含在第 $i-1$ 和第 $i$ 列的边中，因为第 $i-1$ 列初始被联通的边，一定不会因为某些操作而在第 $i$ 列中不联通，若有这些操作一定是不优的。因此在情况可能不变也可能更优的情况下，接下来两列一定不会选择之前没有被使用过的边，这同样是不优的。

因此，在边数较多时，可以先对于前两列跑一次最小生成树，非树边可以直接扔掉。

接着我们只需要考虑接下来两列比前两列少掉哪些边就可以了。我们发现正常去做的话非常难以维护删去边的权值，即保留边的权值。又发现边权范围较小，可以考虑差分思想，每次处理权值 $\le i$​​​ 的边，这些边每成功多联通了两个联通块，就令 $dif++$​​​，这样相当于边权为 $1$​​​ 的边能创造 $29$​​​ 的差分贡献，边权为 $2$​​​ 的边能创造 $28$​​​ 的差分贡献（最后是需要减去差分贡献的），以此类推。

回到去哪些边的问题。同样是每次处理权值 $\le i$ 的边。以第一二列转移到第二三列为例，如果第一二列中的某些边使第 $2$ 列中的某些点联通了，例如使点 $u$ 和点 $v$ 联通，而如果原来的连边也能够使点 $u$ 和点 $v$ 联通，那么这些边就组成了环，即需要去掉一条边。显然 $i$ 越大出现这样的情况越好，因为我们希望删掉的边尽可能大，因此这次这些被断的边对于差分数组的贡献是负的，即使 $dif–$，如果我们删掉了一条边权为 $1$ 的边，他对差分数组就会产生 $-29$ 的贡献。

问题来了，明明是删边，怎么贡献还少了呢？其实是没有问题的，因为第一二列之间需要连 $2n-1$ 条边，而第二三列之间本来就只需要连 $n$ 条边，因此一定会有一些边被删去，只是删的边不同贡献不同而已。

那么后面几列怎么理解呢？可以认为由于某些点初始被连上了，导致从 $2n-1$​ 删到 $n$​ 条边的过程中你所删除的边是权值较小的，可以抽象的认为你用一条边权为 $30$ 的边取代了他，因此他会给差分数组继续产生负贡献。

最后，将差分数据求前缀和求出原数组，再将原数组求前缀和求出前缀和数组，再输出答案即可。

讲得比较抽象，但是以我的水平好像也只能抽象理解了qwq。

代码

代码参考：zyy。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
struct edge{
    int u,v,w;
}e[N],ee[N],E[N];
int fa[N],n,Q,m;
ll dif[N];
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline bool cmp(edge i,edge j){
    return i.w<j.w;
}
inline int find(int x){
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}
inline int read(){
    int x=0;
    char ch=gc();
    for (;ch<48||ch>57;ch=gc());
    for (;ch>=48&&ch<=57;ch=gc())
        x=x*10+ch-48;
    return x;
}
signed main(){
    n=read();Q=read();m=read();
    for(int i=1;i<=m;i++)
        e[i].u=read(),e[i].v=read(),e[i].w=read();
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=2*n;i++) fa[i]=i;
    int cnt=0;
    for(int i=1;i<=m;i++){
        int u=find(e[i].u),v=find(e[i].v+n);
        if(u!=v){
            fa[u]=v;
            e[++cnt]=e[i];
        }
    }
    m=cnt;
    for(int i=2;i<=30;i++){
        cnt=0;
        for(int j=1;j<=2*n;j++) fa[j]=j;
        for(int j=1;j<=m;j++){
            if(e[j].w<i){
                int u=find(e[j].u),v=find(e[j].v+n);
                if(u!=v){
                    dif[1]++;
                    if(u>v) swap(u,v);
                    fa[u]=v;
                    if(u>n) E[++cnt]=(edge){u-n,v-n,0};
                }
            }
            else break;
        }
        for(int j=2;j<=Q;j++){
            if(!cnt) break;
            int tot=cnt;cnt=0;
            for(int k=1;k<=tot;k++){
                int u=find(E[k].u),v=find(E[k].v);
                if(u==v) dif[j]--;
                else{
                    if(u>v) swap(u,v);
                    fa[u]=v;
                    if(u>n) E[++cnt]=(edge){u-n,v-n,0};
                }
            }
        }
    }
    for(int i=2;i<=Q;i++) dif[i]+=dif[i-1];
    for(int i=2;i<=Q;i++) dif[i]+=dif[i-1];
    for(int i=1;i<=Q;i++){
        printf("%lld\n",30*((ll)n*(i+1)-1)-dif[i]);
    }
    return 0;
}