自动搬运

查看原文

来自洛谷，原作者为

	fyxblyn rp++

搬运于2025-08-24 23:16:57，当前版本为作者最后更新于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;
}