【CF2021E】Digital Village（All Version）

题目

给你一张

     n 
    
   
  
    n 
   
  
n 个点  
 
  
   
   
     m 
    
   
  
    m 
   
  
m 条边的无向图，有  
 
  
   
   
     p 
    
   
  
    p 
   
  
p 个关键点。你需要选择  
 
  
   
   
     k 
    
   
  
    k 
   
  
k 个点染黑，使得这  
 
  
   
   
     p 
    
   
  
    p 
   
  
p 个关键点到这  
 
  
   
   
     k 
    
   
  
    k 
   
  
k 个黑点的代价和最小。定义代价为两点之间边权最大的边的最小值。

你需要求出 k = 1,2,…,n 的所有答案

E1 n,m,p<=400
E2 n,m,p<=5000
E3 n,m,p<=2e5

传送门

E1 & E2

两点之间最大边权最小值让你想到了什么？最小生成树。
但是这玩意直接在最小生成树上也不好做啊。但是如果是 kruskal 重构树呢？
显然，两个点

     ( 
    
   
     u 
    
   
     , 
    
   
     v 
    
   
     ) 
    
   
  
    (u,v) 
   
  
(u,v) 之间的代价就是重构树上的  
 
  
   
   
     v 
    
   
     a 
    
    
    
      l 
     
     
     
       l 
      
     
       c 
      
     
       a 
      
     
       ( 
      
     
       u 
      
     
       , 
      
     
       v 
      
     
       ) 
      
     
    
   
  
    val_{lca(u,v)} 
   
  
vallca(u,v)​。

这样我们就可以愉快的dp啦！

设

     d 
    
    
    
      p 
     
     
     
       u 
      
     
       , 
      
     
       i 
      
     
    
   
  
    dp_{u,i} 
   
  
dpu,i​ 为以  
 
  
   
   
     u 
    
   
  
    u 
   
  
u 为根的子树，染黑了  
 
  
   
   
     i 
    
   
  
    i 
   
  
i 个关键点的最小代价。

转移要讨论这棵树有没有染黑任何一个点，如果没有的话整棵树的代价就是

     s 
    
   
     i 
    
   
     z 
    
   
     × 
    
   
     v 
    
   
     a 
    
   
     l 
    
   
  
    siz\times val 
   
  
siz×val，其中  
 
  
   
   
     s 
    
   
     i 
    
   
     z 
    
   
  
    siz 
   
  
siz 为子树内关键点的个数。

做个树上背包就行啦。时间复杂度

     O 
    
   
     ( 
    
    
    
      n 
     
    
      2 
     
    
   
     ) 
    
   
  
    O(n^2) 
   
  
O(n2)

#include<bits/stdc++.h>#defineintlonglongusingnamespace std;constint N=1e6+7,inf=1e18,mod=998244353;int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz;
vector<vector<int>> e,dp;intgf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}voiddfs(int u,int fa){
    dp[u].assign(1,inf);if(bz[u]){
        siz[u]=1;
        dp[u].push_back(0);}for(auto v:e[u]){if(v==fa)continue;dfs(v,u);
        vector<int>dpn(siz[u]+siz[v]+1,inf);for(int i=1; i<=siz[u]+siz[v]; i++){for(int j=max(0ll,i-siz[u]); j<=min(i,siz[v]); j++){if(j==0){
                    dpn[i]=min(dpn[i],dp[u][i-j]+val[u]*siz[v]);}elseif(i==j){
                    dpn[i]=min(dpn[i],dp[v][j]+val[u]*siz[u]);}else{
                    dpn[i]=min(dpn[i],dp[u][i-j]+dp[v][j]);}}}
        siz[u]+=siz[v];
        dp[u]=dpn;}}voidO_o(){
    cin>>n>>m>>k;
    bz.assign(2*n,0);for(int i=1; i<=k; i++){int x;
        cin>>x;
        bz[x]=1;}
    vector<array<int,3>> edge;//l,x,yfor(int i=1; i<=m; i++){int x,y,l;
        cin>>x>>y>>l;
        edge.push_back({l,x,y});}sort(edge.begin(),edge.end());
    fa.assign(2*n,0);for(int i=1; i<=2*n; i++) fa[i]=i;int rt=n;
    e.assign(2*n,vector<int>());
    val.assign(2*n,0);for(auto[l,x,y]:edge){int u=gf(x),v=gf(y);if(u==v)continue;
        rt++;
        fa[u]=rt;
        fa[v]=rt;
        val[rt]=l;
        e[rt].push_back(u);
        e[rt].push_back(v);}
    dp.assign(2*n,vector<int>());
    siz.assign(2*n,0);dfs(rt,0);for(int i=1; i<=min(k,n); i++)
        cout<<dp[rt][i]<<" ";for(int i=k+1; i<=n; i++)
        cout<<"0 ";
    cout<<"\n";}signedmain(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout<<fixed<<setprecision(12);int T=1;
    cin>>T;while(T--){O_o();}}

这个树上背包似乎很难继续优化了呢。我们必须从题目更深的性质去思考问题。
在解决 E3 之前，我们不妨先看一下这道题：

CCPC2024 山东邀请赛 F

这是一道签到题。
可以发现，这个式子可以拆成

     k 
    
   
  
    k 
   
  
k 段后缀和之和，并且其中一段后缀和必须是整个序列。

所以直接把后缀和排个序，选出前

     k 
    
   
     − 
    
   
     1 
    
   
  
    k-1 
   
  
k−1 大的后缀和，再加上整个序列的和即可。

E3

在题目中，一个点都不染色是不合法的，代价应该为

     i 
    
   
     n 
    
   
     f 
    
   
  
    inf 
   
  
inf，但这不利于我们解题。

我们不妨假设他们每一条路径都经过了最大的那条边，也就是初始答案

     a 
    
   
     n 
    
   
     s 
    
   
     = 
    
   
     s 
    
   
     i 
    
    
    
      z 
     
     
     
       r 
      
     
       t 
      
     
    
   
     ∗ 
    
   
     v 
    
   
     a 
    
    
    
      l 
     
     
     
       r 
      
     
       t 
      
     
    
   
  
    ans=siz_{rt}*val_{rt} 
   
  
ans=sizrt​∗valrt​

把样例的重构树画出来，观察一下染黑了一个叶子，对答案会有什么影响？
不太好看出来？由那道签到题的启发，给

     v 
    
   
     a 
    
   
     l 
    
   
  
    val 
   
  
val 做个树上差分试试？

可以发现，从叶子结点到根的那条路径上，

     v 
    
   
     a 
    
    
    
      l 
     
     
     
       f 
      
     
       a 
      
     
    
   
     − 
    
   
     v 
    
   
     a 
    
    
    
      l 
     
    
      u 
     
    
   
  
    val_{fa}-val_{u} 
   
  
valfa​−valu​ 的计算次数都被减少了  
 
  
   
   
     s 
    
   
     i 
    
    
    
      z 
     
    
      u 
     
    
   
  
    siz_u 
   
  
sizu​

再染一个点试试？可以发现，从叶子结点，一直到已经被选择过的那条链为止，

     v 
    
   
     a 
    
    
    
      l 
     
     
     
       f 
      
     
       a 
      
     
    
   
     − 
    
   
     v 
    
   
     a 
    
    
    
      l 
     
    
      u 
     
    
   
  
    val_{fa}-val_{u} 
   
  
valfa​−valu​ 的计算次数都被减少了  
 
  
   
   
     s 
    
   
     i 
    
    
    
      z 
     
    
      u 
     
    
   
  
    siz_u 
   
  
sizu​。

问题就转换成了，你要在树上选出减少答案前

     k 
    
   
  
    k 
   
  
k 大，互不相交的链。

是不是很像树链剖分？
没错，我们把

     ( 
    
   
     v 
    
   
     a 
    
    
    
      l 
     
     
     
       f 
      
     
       a 
      
     
    
   
     − 
    
   
     v 
    
   
     a 
    
    
    
      l 
     
    
      u 
     
    
   
     ) 
    
   
     ∗ 
    
   
     s 
    
   
     i 
    
    
    
      z 
     
    
      u 
     
    
   
  
    (val_{fa}-val_{u})*siz_u 
   
  
(valfa​−valu​)∗sizu​ 作为  
 
  
   
   
     ( 
    
   
     u 
    
   
     , 
    
   
     f 
    
    
    
      a 
     
    
      u 
     
    
   
     ) 
    
   
  
    (u,fa_u) 
   
  
(u,fau​) 的边权，对整棵树做长链剖分（jiangly：这是典中典长链剖分题）。

把所有的长链的权值排序，然后每次选出前

     k 
    
   
  
    k 
   
  
k 大减去就做完啦！

#include<bits/stdc++.h>#defineintlonglongusingnamespace std;constint N=1e6+7,inf=1e18,mod=998244353;int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz,p;
vector<vector<int>> e;intgf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}intdfs(int u,int fa){if(bz[u]){
        siz[u]=1;}int mx=0;for(auto v:e[u]){int res=dfs(v,u);
        siz[u]+=siz[v];if(mx<res)swap(res,mx);
        p.push_back(res);}if(fa!=0)
        mx+=siz[u]*(val[fa]-val[u]);return mx;}voidO_o(){
    cin>>n>>m>>k;
    bz.assign(2*n,0);for(int i=1; i<=k; i++){int x;
        cin>>x;
        bz[x]=1;}
    vector<array<int,3>> edge;//l,x,yfor(int i=1; i<=m; i++){int x,y,l;
        cin>>x>>y>>l;
        edge.push_back({l,x,y});}sort(edge.begin(),edge.end());
    fa.assign(2*n,0);for(int i=1; i<=2*n; i++) fa[i]=i;int rt=n;
    e.assign(2*n,vector<int>());
    val.assign(2*n,0);for(auto[l,x,y]:edge){int u=gf(x),v=gf(y);if(u==v)continue;
        rt++;
        fa[u]=rt;
        fa[v]=rt;
        val[rt]=l;
        e[rt].push_back(u);
        e[rt].push_back(v);}
    siz.assign(2*n,0);
    p.clear();
    p.push_back(dfs(rt,0));int ans=k*val[rt];sort(p.begin(),p.end(),greater<>());for(int i=0; i<n; i++){
        ans-=p[i];
        cout<<ans<<" ";}
    cout<<"\n";}signedmain(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout<<fixed<<setprecision(12);int T=1;
    cin>>T;while(T--){O_o();}}