CF2021E3 Digital Village (Extreme Version)

原题链接

考虑建出 kruskal 重构树，设 \(f_{i,j}\) 为 \(i\) 子树中选了 \(j\) 个点的答案最小值。记 \(cnt_x\) 为 \(x\) 子树中有多少个关键点，\(w_x\) 为 kruskal 重构树上的权值。

转移时合并两个子树 \(f_{x,i}=\min f{u,j}+f{v_{i-j}}\)，还有一种转移是 \(f_{x,i}=f_{v,i}+cnt_{u}\times w_x\)，意义是所有左子树中的点都要跑到右子树中去，经过的最大的边权就是 \(w_x\)。另一侧同理。

所以实际上我们每次转移后 \(f_{x,0}\gets cnt_x\times w_{fa_x}\)，然后就是 \((\min,+)\) 卷积的形式，显然有凸性，可以闵可夫斯基和优化。

我们考虑记录 \(f_{x,i}-f_{x,i+1}(i\in[0,siz_x-1])\)，这个单调递减。每次手动给 \(f_{x,0}\) 赋值时相当于将最大值拿出来加上 \(cnt_x\times (w_{fa_x}-w_x)\)，因为修改前的 \(f_{x,0}=f_{u,0}+f_{v,0}=cnt_x\times w_x\)，所以需要取出来最大值。于是 set 启发式合并即可，时间复杂度 \(O(n\log^2 n)\)。

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#define ll long long
using namespace std;
const int MAXN=4e5+10;
int T,n,m,p,s[MAXN],cnt[MAXN],siz[MAXN],fa[MAXN],w[MAXN];
int u[MAXN],v[MAXN],R[MAXN];ll ans[MAXN];multiset <ll> f[MAXN];
struct node{int x,y,w;}e[MAXN];
inline bool cmp(node x,node y){return x.w<y.w;}
inline int find(int x)
    {return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int x,int fa=0)
{
    if(!u[x]&&!v[x])
        {f[R[x]=x].insert(cnt[x]*w[fa]),siz[x]=1;return ;}
    dfs(u[x],x),dfs(v[x],x);
    cnt[x]=cnt[u[x]]+cnt[v[x]],siz[x]=siz[u[x]]+siz[v[x]];
    if(siz[u[x]]>siz[v[x]]) swap(u[x],v[x]);
    R[x]=R[v[x]];int p=R[u[x]];
    for(auto it=f[p].begin();it!=f[p].end();++it)
        f[R[x]].insert(*it);
    f[p].clear();auto it=f[R[x]].end();--it;
    ll W=*it+1ll*cnt[x]*(w[fa]-w[x]);
    f[R[x]].erase(it);if(fa) f[R[x]].insert(W);
}
inline void work()
{
    cin>>n>>m>>p;
    for(int i=1;i<=(n<<1);++i)
        fa[i]=i,u[i]=v[i]=cnt[i]=0;
    for(int i=1;i<=p;++i)
        cin>>s[i],cnt[s[i]]=1;
    for(int i=1;i<=m;++i)
        cin>>e[i].x>>e[i].y>>e[i].w;
    sort(e+1,e+1+m,cmp);int tot=n;
    for(int i=1;i<=m;++i)
    {
        if(find(e[i].x)==find(e[i].y)) continue;
        int fax=find(e[i].x),fay=find(e[i].y);
        w[++tot]=e[i].w,fa[u[tot]=fax]=fa[v[tot]=fay]=tot;
    }
    ans[n]=0;dfs(tot);auto it=f[R[tot]].begin();
    for(int i=n-1;i;--i) ans[i]=ans[i+1]+*it,++it;
    for(int i=1;i<=n;++i) cout<<ans[i]<<' ';
    cout<<'\n';f[R[tot]].clear();return ;
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>T;while(T--) work();return 0;
}