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

Sonetto37 · 2026-10-21 20:22:10 · 题解

感觉按照我这个思路看下来，这道题最多只有蓝。

数据结构题。

肯定地，为了满足题目的购买个数的条件，又想让总成本最小，肯定是每棵子树都刚好满足题目条件。

那么我们考虑对于每棵子树中，直接处理。考虑在先前的基础上，若还需要购买，那就找最小的 c_i 是否能加就行了。不能再找次小的，以此类推。

这个东西树链剖分加线段树和可并堆来维护就行了。

可并堆用的是左偏树来写的。

因为在可并堆里的数只会加入一次和删去一次，所以时间复杂度是可以得到保证的。

粗略分析下来，每次 solve 的时间复杂度是 O(n\log^2(n))。

#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace _ {

    const int N = 2e5+10;
    const int inf = 0x3f3f3f3f3f3f3f3f;

    struct SegTree {

        int mi[4*N], tag[4*N];

        void doBuild(int k, int l, int r) {
            tag[k] = mi[k] = 0;
            if (l == r) return;
            int mid = (l + r) >> 1;
            doBuild(k*2, l, mid);
            doBuild(k*2+1, mid+1, r);
        }

        void doBuild(int k, int l, int r, int a[], int p[]) {
            tag[k] = 0;
            if (l == r) { mi[k] = a[p[l]]; return; }
            int mid = (l + r) >> 1;
            doBuild(k*2, l, mid, a, p);
            doBuild(k*2+1, mid+1, r, a, p);
            mi[k] = min(mi[k*2], mi[k*2+1]);
        }

        void doChangeOne(int k, int l, int r, int dx) {
            mi[k] += dx, tag[k] += dx;
        }

        void pushDown(int k, int l, int r) {
            if (tag[k] == 0) return;
            int mid = (l + r) >> 1;
            doChangeOne(k*2, l, mid, tag[k]);
            doChangeOne(k*2+1, mid+1, r, tag[k]);
            tag[k] = 0;
        }

        void doChange(int k, int l, int r, int x, int y, int dx) {
            if (r < x || y < l) return;
            if (x <= l && r <= y) { doChangeOne(k, l, r, dx); return; }
            pushDown(k, l, r);
            int mid = (l + r) >> 1;
            doChange(k*2, l, mid, x, y, dx);
            doChange(k*2+1, mid+1, r, x, y, dx);
            mi[k] = min(mi[k*2], mi[k*2+1]);
        }

        int doQuery(int k, int l, int r, int x, int y) {
            if (r < x || y < l) return inf;
            if (x <= l && r <= y) return mi[k];
            pushDown(k, l, r); int mid = (l + r) >> 1;
            return min(doQuery(k*2, l, mid, x, y), doQuery(k*2+1, mid+1, r, x, y));
        }
    } Seg;

    struct SegTree2 {

        int sum[4*N], tag[4*N];

        void doBuild(int k, int l, int r) {
            tag[k] = sum[k] = 0;
            if (l == r) return;
            int mid = (l + r) >> 1;
            doBuild(k*2, l, mid);
            doBuild(k*2+1, mid+1, r);
        }

        void doChangeOne(int k, int l, int r, int dx) {
            sum[k] += (r-l+1)*dx, tag[k] += dx;
        }

        void pushDown(int k, int l, int r) {
            if (tag[k] == 0) return;
            int mid = (l + r) >> 1;
            doChangeOne(k*2, l, mid, tag[k]);
            doChangeOne(k*2+1, mid+1, r, tag[k]);
            tag[k] = 0;
        }

        void doChange(int k, int l, int r, int x, int y, int dx) {
            if (r < x || y < l) return;
            if (x <= l && r <= y) { doChangeOne(k, l, r, dx); return; }
            pushDown(k, l, r);
            int mid = (l + r) >> 1;
            doChange(k*2, l, mid, x, y, dx);
            doChange(k*2+1, mid+1, r, x, y, dx);
            sum[k] = sum[k*2] + sum[k*2+1];
        }

        int doQuery(int k, int l, int r, int x, int y) {
            if (r < x || y < l) return 0;
            if (x <= l && r <= y) return sum[k];
            pushDown(k, l, r); int mid = (l + r) >> 1;
            return doQuery(k*2, l, mid, x, y) + doQuery(k*2+1, mid+1, r, x, y);
        }
    } Seg2;

    int n;
    int p[N];

    vector<int> g[N];

    int c[N];
    int l[N], r[N];

    int b[N];

    int siz[N], hson[N], top[N];

    int tim, dfn[N], id[N];

    bool flag = false;

    int hc[N], hid[N];
    int lt[N], rt[N], dis[N];

    int nowpos;
    int root[N]; 

    int makeNode(int cc, int idd) {
        int x = ++nowpos;
        hc[x] = cc; hid[x] = idd;
        lt[x] = rt[x] = 0;
        dis[x] = 1;
        return x;
    }

    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (hc[x] > hc[y] || (hc[x] == hc[y] && hid[x] > hid[y]))
            swap(x, y);
        rt[x] = merge(rt[x], y);
        if (dis[lt[x]] < dis[rt[x]]) swap(lt[x], rt[x]);
        dis[x] = dis[rt[x]] + 1;
        return x;
    }

    bool empty(int u) { 
        return root[u] == 0; 
    }

    int topC(int u) { 
        return hc[root[u]]; 
    }

    int topId(int u) { 
        return hid[root[u]]; 
    }

    void pop(int u) {
        root[u] = merge(lt[root[u]], rt[root[u]]);
    }

    void Union(int u, int v) {
        root[u] = merge(root[u], root[v]);
        root[v] = 0;
    }

    void clear() {
        Seg.doBuild(1, 1, n);
        Seg2.doBuild(1, 1, n);
        for (int i = 1; i <= n; i++) {
            root[i] = 0;
            l[i] = r[i] = c[i] = b[i] = p[i] = 0;
            g[i].clear(); siz[i] = hson[i] = top[i] = dfn[i] = id[i] = 0;
        }
        nowpos = 0;
        tim = 0;
    }

    int query(int u, int fath) {
        int res = inf;
        while (dfn[top[u]] > dfn[fath]) {
            res = min(res, Seg.doQuery(1, 1, n, dfn[top[u]], dfn[u]));
            u = p[top[u]];
        }
        res = min(res, Seg.doQuery(1, 1, n, dfn[fath], dfn[u]));
        return res;
    }

    void dfs(int u, int from) {
        siz[u] = 1;
        for (int v : g[u]) {
            if (v == from) continue;
            dfs(v, u); siz[u] += siz[v];
            if (siz[v] >= siz[hson[u]]) hson[u] = v;
        }
    }

    void dfs2(int u, int from, int tp) {
        id[dfn[u] = ++tim] = u, top[u] = tp;
        if (hson[u]) dfs2(hson[u], u, tp);
        for (int v : g[u]) {
            if (v == from || v == hson[u]) continue;
            dfs2(v, u, v);
        }
    }

    void add(int u, int fath, int dx) {
        while (dfn[top[u]] > dfn[fath]) {
            Seg.doChange(1, 1, n, dfn[top[u]], dfn[u], -dx);
            Seg2.doChange(1, 1, n, dfn[top[u]], dfn[u], dx);
            u = p[top[u]];
        }
        Seg.doChange(1, 1, n, dfn[fath], dfn[u], -dx);
        Seg2.doChange(1, 1, n, dfn[fath], dfn[u], dx);
    }

    void calc(int u, int from) {
        if (flag) return;

        for (int v : g[u]) {
            if (v == from) continue;
            calc(v, u);
        }
        if (flag) return;

        root[u] = merge(root[u], makeNode(c[u], u));

        for (int v : g[u]) {
            if (v == from) continue;
            int pp = Seg2.doQuery(1, 1, n, dfn[v], dfn[v]);
            Seg2.doChange(1, 1, n, dfn[u], dfn[u], pp);
            Seg.doChange (1, 1, n, dfn[u], dfn[u], -pp);  
            Union(u, v);
        }

        if (Seg2.doQuery(1, 1, n, dfn[u], dfn[u]) > r[u]) {
            flag = true;
            return;
        }

        while (Seg2.doQuery(1, 1, n, dfn[u], dfn[u]) < l[u]) {
            if (empty(u)) {
                flag = true;
                return;
            }
            int cc = topC(u), idd = topId(u);
            int most = query(idd, u);
            int need = l[u] - Seg2.doQuery(1, 1, n, dfn[u], dfn[u]);

            if (most <= need) {
                add(idd, u, most);
                b[idd] += most;
                pop(u); 
            } else {
                add(idd, u, need);
                b[idd] += need;
            }
        }
    }

    void solve() {
        cin >> n;
        for (int i = 2; i <= n; i++) {
            cin >> p[i];
            g[i].push_back(p[i]);
            g[p[i]].push_back(i);
        }
        for (int i = 1; i <= n; i++) cin >> c[i];
        for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];

        dfs(1, 0);
        dfs2(1, 0, 1);

        Seg.doBuild(1, 1, n, r, id);
        Seg2.doBuild(1, 1, n);

        flag = false;
        calc(1, 0);

        if (flag) cout << -1 << '\n';
        else {
            int ans = 0;
            for (int i = 1; i <= n; i++) ans += c[i] * b[i];
            cout << ans << '\n';
            for (int i = 1; i <= n; i++) cout << b[i] << " ";
            cout << '\n';
        }
    }

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

signed main() {
    return _::main();
}