题解：P12627 [NAC 2025] Ornaments on a Tree

fyxblyn · 2025-07-08 20:02:09 · 题解

题意

给定一颗有 N 个节点的树，其中一些点的点权已经确定，为剩下节点确定一个非负整数点权，使得没有任何节点及其直接子节点点权之和大于 K，并使所有节点点权之和最大。

思路

记 sum_i 为节点 i 及其所有直接子节点的点权之和。

由于点权可以为 0，判断无解时只需要看已经确定点权的点有没有超出限制即可。

显然，处理一个节点的点权时只需考虑它自身（设为 i）和其父节点（设为 fa），即保证 sum_i 和 sum_{fa} 不超过 K，这启发我们由下往上进行处理。

由于需要最大化点权之和，i 的点权自然越大越好，所以我们得到节点 i 的最优点权为：

这保证能在 i 节点处获得局部最优，同时因为 i 与 fa 的父节点无关，这个局部最优即可推广到全局最优。

注意记录已经确定点权的点，并在处理时直接跳过它们。

具体实现可以参考代码。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e5+5;
struct node
{
    int v,nt;
}e[N];
int head[N],tot;
void add(int u,int v)
{
    e[++tot]={v,head[u]};
    head[u]=tot;
}
int a[N],sum[N],f[N],flag[N];
void dfs1(int u,int fa)
{
    f[u]=fa;
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].v;
        if(v==fa)continue;
        sum[u]+=a[v];
        dfs1(v,u);
    }
}
int n,m;
void dfs2(int u)
{
    for(int i=head[u];i;i=e[i].nt)
    {
        int v=e[i].v;
        if(v==f[u])continue;
        dfs2(v);
    }
    if(flag[u])return;
    int num=min(m-sum[u],m-sum[f[u]]);
    a[u]+=num,sum[u]+=num,sum[f[u]]+=num;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==-1)a[i]=0;
        else flag[i]=1;
        sum[i]=a[i];
    }
    for(int i=1,u,v;i<n;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(1,1);
    for(int i=1;i<=n;i++)
    {
        if(sum[i]>m)
        {
            cout<<"-1";
            return 0;
        }
    }
    dfs2(1);
    int ans=0;
    for(int i=1;i<=n;i++)ans+=a[i];
    cout<<ans;
    return 0;
}