洛谷5521 [yLOI2019] 梅深不见冬

题意

有一棵 $n(\le 100004)$ 个点的树，从根节点出发。节点 $x$ 能放梅花，仅当其所有子节点 $y$ 上都放了 $w_y$ 朵梅花。对于 $\forall i\in [1,n]$ ，如果要在 $i$ 上放 $w_i$ 朵梅花，则至少需要在过程中准备多少梅花？

题解

可以发现对于节点 $x$ ，一定是按某种顺序遍历所有子节点 $y$ 放上梅花，而且不同的顺序得到的答案也不相同。

考虑DP，用 $f[x]$ 表示在 $x$ 上放上梅花的最小答案。如果在第 $i$ 次放节点 $y_i$ ，那么所需的代价为

$$\sum_{j=1}^{i-1} w[y_j]+f[y_i]$$

即前面 $i-1$ 个节点都已经放上，这次遍历以 $y_i$ 为根的子树的代价为 $f[y_i]$ 。$f[x]$ 即为这些代价的最大值。

考虑遍历的顺序，用类似国王游戏的贪心方法。对于第 $i$ 个和第 $i+1$ 个，它们原先的代价（去掉 $\sum_{j=1}^{i-1} w[y_j]$）为 $w[i]+f[i+1]$ ，交换后为 $w[i+1]+f[i]$ ，即要求满足：

$$w[i]+f[i+1]<w[i+1]+f[i]$$

$$f[i]-w[i]>f[i+1]-w[i+1]$$

那么按 $f[y]-w[y]$ 从大到小排序就行了。

#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define ll long long

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=100005;

vector <int> v[N];
int n,m,a,b,w[N],f[N];

inline bool cmp(int x,int y) { return f[x]-w[x]>f[y]-w[y]; }

void dfs(int x)
{
    if (!v[x].size()) return (void)(f[x]=w[x]);
    int &res=f[x]=w[x];
    for (auto y:v[x])
    {
        dfs(y);
        res+=w[y];
    }
    sort(v[x].begin(),v[x].end(),cmp);
    int sum=0;
    for (auto y:v[x])
    {
        res=max(res,f[y]+sum);
        sum+=w[y];
    }
}

signed main()
{
    n=read();
    for (int i=2;i<=n;i++) v[read()].emplace_back(i);
    for (int i=1;i<=n;i++) w[i]=read();
    dfs(1);
    for (int i=1;i<=n;i++) printf("%d ",f[i]);
    return 0;
}