专栏文章

题解：P11097 [ROI 2022] 采购优化 (Day 1)

ssintle
P11097题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minhfwia
此快照首次捕获于
2025/12/02 02:28
3 个月前
此快照最后确认于
2025/12/02 02:28
3 个月前
查看原文

原题链接

题意简述

给出一棵树，每个节点 ii 有代价 cic_i，并且给出区间 [li,ri][l_i,r_i] 要求该节点子树内的权值和在该区间内。
要决定每个点的权值，使得满足给出的条件，并且每个节点的权值乘代价之和最小，给出一种方案。

解题思路

宝宝题，但是我假了 114514 发。
注意到多选点一定不优，所以满足最低要求就好了。考虑对于每个节点，其子树内节点对当前节点的贡献。
首先满足每个点的最低要求，显然如果存在一个点 ii，使得其子节点满足最低要求之后的和超过 rir_i，则无解。
设所有子节点为根的子树内满足条件后的权值之和为 sumisum_i，则要使 sumisum_i 满足条件必须多选出几个点，显然贪心选一定是正确的。
对于每个节点维护一坨三元组 {val,cnt,id}\{val,cnt,id\} 表示在不超出子树内限制的情况下，可以添加 cntcnt 个代价为 valval 的点，位置在 idid。
将子节点合并到父节点可以使用启发式合并，加上维持有序，开销是两只老哥。考虑怎么维护当前节点使得无论怎么选都不会超出子树内限制。
显然可以维护三元组使所有三元组的 cntcnt 之和恰好为 ri−max⁡(li,sumi)r_i-\max(l_i,sum_i)（注意这里要把代价为 cic_i 的三元组也加进去），从后往前删去权值大的点直到满足条件即可。

复杂度分析

本题复杂度构成可以分成两个部分：
  • 启发式合并：O(nlog⁡2n)O(n\log^2n)
  • 贪心选点/删点：由于每个三元组最多被删除一次，且每个节点最多插入 22 个三元组，故复杂度为 O(nlog⁡n)O(n\log n)
因此本题的时间复杂度为 O(nlog⁡2n)O(n\log^2n)。

参考代码

CPP
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 100005;
ll T , n , fa[N] , c[N] , L[N] , R[N] , sum[N] , ans[N] , f[N] , ssum[N];
struct point
{
    ll val , num , id;
    bool operator <(const point &b) const
    {
        if(val != b.val) return val < b.val;
        if(num != b.num) return num < b.num;
        return id < b.id;
    }
};
set <point> s[N];
vector<ll> g[N];
bool flag;

void dfs(ll u)
{
    sum[u] = f[u] = ssum[u] = ans[u] = 0;
    for(auto v : g[u])
    {
        dfs(v); sum[u] += sum[v]; f[u] += f[v]; ssum[u] += ssum[v];
        if(s[v].size() > s[u].size()) swap(s[u] , s[v]);
        while(!s[v].empty()) s[u].insert(*s[v].begin()) , s[v].erase(s[v].begin());
    }
    if(sum[u] > R[u]) return flag = 1 , void();
    while(sum[u] < L[u])
    {
        if(!s[u].empty() && s[u].begin()->val < c[u])
        {
            auto [val , num , id] = *s[u].begin(); s[u].erase(s[u].begin());
            ssum[u] -= num;
            if(sum[u] + num > L[u])
            {
                ll tmp = L[u] - sum[u];
                num -= tmp; ans[id] += tmp;
                f[u] += tmp * val; sum[u] = L[u];
                s[u].insert({val , num , id});
                ssum[u] += num;
            }
            else
            {
                sum[u] += num; ans[id] += num;
                f[u] += num * val;
            }
        }
        else
        {
            ll tmp = L[u] - sum[u]; sum[u] = L[u];
            ans[u] += tmp; f[u] += tmp * c[u];
        }
    }
    ll tot = R[u] - sum[u];
    while(!s[u].empty() && prev(s[u].end())->val > c[u])
        ssum[u] -= prev(s[u].end())->num,
        s[u].erase(prev(s[u].end()));
    while(ssum[u] > tot && !s[u].empty())
    {
        auto it = --s[u].end(); s[u].erase(it);
        auto [val , num , id] = *it;
        if(ssum[u] - num < tot)
        {
            num -= ssum[u] - tot;
            ssum[u] = tot;
            s[u].insert({val , num , id});
        }
        else ssum[u] -= num;
    }
    if(ssum[u] < tot) s[u].insert({c[u] , tot - ssum[u] , u}) , ssum[u] = tot;
}

void solve()
{
    cin >> n; flag = 0;
    for(ll i = 2 ; i <= n ; i++) cin >> fa[i] , g[fa[i]].emplace_back(i);
    for(ll i = 1 ; i <= n ; i++) cin >> c[i];
    for(ll i = 1 ; i <= n ; i++) cin >> L[i] >> R[i];
    dfs(1); cout << (flag ? -1 : f[1]) << '\n';
    if(!flag) for(ll i = 1 ; i <= n ; i++) cout << ans[i] << ' '; cout << '\n';
    for(ll i = 1 ; i <= n ; i++) s[i].clear() , g[i].clear();
}

signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> T; while(T--) solve();
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...