自动搬运

查看原文

来自洛谷，原作者为

	huangleyi0129 Keep dreaming, remain loving.

搬运于2025-08-24 22:59:08，当前版本为作者最后更新于2025-02-05 22:56:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

直接考虑 $O(n)$ 的做法。

对于每个点 $u$，删去 $u$ 后形成的每一联通块都要有点被选择，显然选最小是不劣的，可以用换根 DP 解决。

设 $deg_u=d$，一共要连 $d-1$ 条边，故还要选 $res=d-3$ 个点，容易证明可以任意选择。

将所以点权扔进桶 $cnt$ 里，从最小非 $0$ 处开始扫，逐次删除，$res\Leftarrow res-cnt_i$，并将 $cnt_i$ 加到 $cnt_{i+1}$ 里。

因为 $res$ 每次操作至少减 $1$，所以单点复杂度 $O(deg_u)$。

$\sum O(deg_u)=O(n)$。目前最优解。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
vector<int>e[N],p;
int w[N],t[N],f[N],g[N],fa[N],n,mn=N,mn2=N;
void dfs(const int k)
{
	f[k]=w[k];
	int mn=w[k],mn2=w[k];
	for(int i:e[k])
		if(i!=fa[k])
		{
			fa[i]=k,dfs(i),f[k]=min(f[k],f[i]);
			if(f[i]<mn)
				mn2=mn,mn=f[i];
			else if(f[i]<mn2)
				mn2=f[i];
		}
	for(int i:e[k])
		if(i!=fa[k])
			if(f[i]==mn)
				g[i]=mn2;
			else
				g[i]=mn;
}
void dfs2(const int k)
{
	for(int i:e[k])
		if(i!=fa[k])
			g[i]=min(g[i],g[k]),dfs2(i);
}
void calc(const int k)
{
	if(p.size()==1)
		return cout<<0<<' ',void();
	int st=mn;
	long long ans=0,s=0,d=p.size()-2;
	if(w[k]==mn)
		st=mn2;
	--t[w[k]];
	for(int i:p)
		ans+=i,--t[i],++t[i+1];
	for(int i=st;d;++i)
	{
		if(d>t[i]+s)
			s+=t[i],d-=s,ans+=s*i;
		else
		{
			ans+=d*i;
			break;
		} 
	}
	for(int i:p)
		++t[i],--t[i+1];
	++t[w[k]];
	cout<<ans<<' ';
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n;
	int u,v;
	for(int i=1; i<=n; ++i)
	{
		cin>>w[i],++t[w[i]];
		if(w[i]<mn)
			mn2=mn,mn=w[i];
		else if(w[i]<mn2)
			mn2=w[i];
	}
	for(int i=1; i<n; ++i)
		cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
	dfs(1);
	g[1]=n+1,dfs2(1);
	for(int i:e[1])
		p.push_back(f[i]);
	calc(1);
	for(int i=2;i<=n;++i)
	{
		p.clear();
		for(int j:e[i])
			if(j!=fa[i])
				p.push_back(f[j]);
		p.push_back(g[i]);
		calc(i);
	}
	return 0;
}