洛谷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;
}