P10555 [ICPC 2024 Xi'an I] Fix the Tree 题解
huangleyi0129
·
·
题解
直接考虑 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)。
代码如下：
```cpp
#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;
}
```