【CF2021E】Digital Village（All Version）

题目

给你一张 $n$ 个点 $m$ 条边的无向图，有 $p$ 个关键点。你需要选择 $k$ 个点染黑，使得这 $p$ 个关键点到这 $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)$ 之间的代价就是重构树上的 $va{l}_{lca(u,v)}$。
这样我们就可以愉快的dp啦！

设 $d{p}_{u,i}$ 为以 $u$ 为根的子树，染黑了 $i$ 个关键点的最小代价。
转移要讨论这棵树有没有染黑任何一个点，如果没有的话整棵树的代价就是 $siz\times val$，其中 $siz$ 为子树内关键点的个数。
做个树上背包就行啦。时间复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353;
int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz;
vector<vector<int>> e,dp;
int gf(int x)
{return x==fa[x]?x:fa[x]=gf(fa[x]);
}
void dfs(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]);}else if(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;}
}
void O_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";
}
signed main()
{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-1$ 大的后缀和，再加上整个序列的和即可。

E3

在题目中，一个点都不染色是不合法的，代价应该为 $inf$，但这不利于我们解题。
我们不妨假设他们每一条路径都经过了最大的那条边，也就是初始答案 $ans=si{z}_{rt}\ast va{l}_{rt}$
把样例的重构树画出来，观察一下染黑了一个叶子，对答案会有什么影响？
不太好看出来？由那道签到题的启发，给 $val$ 做个树上差分试试？
可以发现，从叶子结点到根的那条路径上，$va{l}_{fa}-va{l}_u$ 的计算次数都被减少了 $si{z}_u$
再染一个点试试？可以发现，从叶子结点，一直到已经被选择过的那条链为止，$va{l}_{fa}-va{l}_u$ 的计算次数都被减少了 $si{z}_u$。
问题就转换成了，你要在树上选出减少答案前 $k$ 大，互不相交的链。
是不是很像树链剖分？
没错，我们把 $(va{l}_{fa}-va{l}_u)\ast si{z}_u$ 作为 $(u,f{a}_u)$ 的边权，对整棵树做长链剖分（jiangly：这是典中典长链剖分题）。
把所有的长链的权值排序，然后每次选出前 $k$ 大减去就做完啦！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18,mod=998244353;
int n,m,k;
vector<bool> bz;
vector<int> val,fa,siz,p;
vector<vector<int>> e;
int gf(int x)
{return x==fa[x]?x:fa[x]=gf(fa[x]);
}
int dfs(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;
}
void O_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";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;cin>>T;while(T--){O_o();}
}