CF 1693B Fake Plastic Tree

标签: cf

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

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

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);
}