CF 1693B Fake Plastic Tree

標籤： cf

给定一棵树，每次操作选取一个从根节点开始的路径，对于路径上的第 $i$ 个点，其值加上 $c_i$，其中 $c$ 是一个不降非负整数序列。最终使得对于第 $i$ 个节点，其值在 $l_i$ 与 $r_i$ 之间。求最少操作数。

考虑贪心，从叶子开始，尽可能让每个节点加的数大。$f_i$ 表示节点 $i$ 所能加上去的最大值。

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<std::vector<int>> g(n + 1);
    std::vector<int> l(n + 1), r(n + 1);
    std::vector<long long> f(n + 1);
    for (int i = 2; i <= n; i++)
    {
        int p;
        scanf("%d", &p);
        g[p].push_back(i);
    }
    for (int i = 1; i <= n; i++) scanf("%d%d", &l[i], &r[i]);
    int ans = 0;
    for (int i = n; i >= 1; i--)
    {
        long long sum = 0;
        f[i] = r[i];
        for (auto j : g[i])
        {
            sum += f[j];
        }   
        if (sum < l[i])
            ans++;
        else
            f[i] = std::min(sum, f[i]);
    }
    printf("%d\n", ans);
}