洛谷P5521 [yLOI2019] 梅深不见冬 题解

题目链接：P5521 [yLOI2019] 梅深不见冬

题意：

给定一棵树，根节点为 \(1\) ，有点权 \(w_i\) ，cxy 想在在结点上放满梅花。

她从这棵树的 \(1\) 号节点出发，沿着树上的边行走。

设当前在 \(u\) ，则 cxy 每次只能走到一个没有走过的儿子结点 \(v\) ，或者回到 \(u\) 的父亲。

当且仅当一个结点 \(u\) 的所有儿子 \(v\) 都放满了 \(w_v\) 朵，才可以在 \(u\) 上放置梅花。

梅花可以随时收回，求每个结点放上梅花的最小花费。

数据范围：

\(1 \leq n \leq 10^5 + 4,~1 \leq w_i \leq 1000\)。

设第 \(i\) 个结点放梅花的最小花费为 \(f_i\) ，不难发现 \[ f_u = \max\left\{ \max_{v \in \text{son(u)}} \left\{f_v + \sum_{k \in \text{son}(u)\, \land \,k \text{ before } v} w_k\right\},w_u + \sum_{v \in \text{son}(u)}w_v\right\} \] 后者是最小花费的下界

观察第一部分 \[ \max_{v \in \text{son(u)}} \left\{f_v + \sum_{k \in \text{son}(u)\, \land \,k \text{ before } v} w_k\right\} \] 这部分显然与 \(\text{son}(u)\) 的排列有关

如何求出这个最优排列？

贪心，按 \(g_u = f_u - w_u\) 降序排序即可

考虑 \(u\) 仅有 \(2\) 个子结点 \(x,y\) 的情况，

设 \(x\) 在 \(y\) 之前更优，则 \[ f_u=\max\{f_x,f_y+w_x\}\le \max\{f_y,f_x+w_y\} \]

• 若 \(f_y + w_x \ge f_x\) ，

  因为 \(f_y + w_x > f_y\) ，所以右侧取 \(f_x+w_y\) 才可能成立

  则可得 \[ f_y + w_x \le f_x + w_y \] 移项得 \[ f_x-w_x \le f_y-w_y \]

• 若 \(f_y + w_x < f_x\)

  则 \(f_x > f_y\)，故右侧取 \(f_x+w_y\) 时才可能成立

  显然有 \(f_x < f_x + w_y\)

综上所述，按 \(g_u = f_u - w_u\) 降序排序可以获得最优解

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

vector<int> son[N];
int n,m,w[N],f[N];
int cmp(int x,int y)
{return f[y]-w[y]<f[x]-w[x];}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=2,u; i<=n; i++)
        cin >> u,son[u].push_back(i);
    for(int i=1; i<=n; i++) cin >> w[i];
    for(int i=n; i>=1; i--)
    {
        sort(son[i].begin(),son[i].end(),cmp);
        int sum=0;
        for(int v : son[i])
            f[i]=max(f[i],f[v]+sum),sum+=w[v];
        f[i]=max(f[i],sum+w[i]);
    }
    for(int i=1; i<=n; i++)
        cout << f[i] << " \n"[i==n];
    return 0;
}