题解：P10759 [BalticOI 2024] Jobs

· · 题解

看到这一题我就想到了另一个题目，对比之下发现，这不就是 P7925 的加强版吗。怪不得那么眼熟。

思路

回归正题，我们考虑如何解决本题。题面很明显给出了一个森林，但并不妨碍，我们建出一个虚根 0 然后当有根树做就行。

首先，根据一个正常人的思维，我们只会在保证能够赚到钱的时候才会进入某个子树内，否则进去只会亏本，还不如不进去。

有了这个前提，我们希望对于每个点求出一个值 f_{u} 表示进入以 u 为根的子树时，我的手上至少要有 f_{u} 的钱数才能赚到钱，如果不可能赚到那么 f_{u}=+\infty。

假设我们已经求出了 f_{u}，对于一个拓展出的确定局面，我们一定是先取用能拓展到的 f_{u} 最小的点（这个可以考虑反证法证明，并不难）。这个事情可以交给堆来完成。考虑如何求答案，我们从根开始拓展，同时维护一个 now 表示当前钱数，一开始将根加入堆中，每次取出一个点，将它的贡献加入当前钱数，然后拓展出它的儿子，将它的儿子加入堆中。重复上述操作直至取出的点有 f_{u}>now，这表明现在不论如何拓展都不可能赚到到更多的钱，那么此时的 now 就是最大钱数，注意到题目要求的是利润，所以要减去 s 才是我们要求的答案。

上述过程为 O(n\log{n})，没有问题。

接下来介绍本题的重点，如何求出 f_{u}。

一个朴素的想法是，我们对于每一个点，采用与求答案类似的方法，从子树的根开始拓展整棵子树，并动态地维护我们的投入钱数 f_{u}，在 now>f_{u} 时，我们可以放心离开，否则就还要拓展下去，因为现在还是亏本的，但是不同的是，如果取出的点 cur 有 f_{cur}>now，由于现在还没有赚到足够的钱，我们必须进入 cur 这个子树，但是又无法在 u 的子树内赚到更多钱了。那么为了赚到更多的钱，我们只有一个办法，加大投资。也就是我们更新 f_{u}，既然现在的 now 不够，那我们就加大投入让它够。具体的，我们将 f_{u} 加上 f_{cur}-now 这样我们就可以将 now 提升至刚好能够到 f_{cur}，能够放心赚钱了。如果自始至终都没有赚到，说明这个子树不可能赚到，令 f_{u}=+\infty 即可。

现在我们就切掉了 P7925。这个过程明显是 O(n^2\log{n}) 的，能够通过我们前面提到的弱化版，但是难以通过本题（实测 TLE 两个点）。

考虑优化，我们发现，在求 f_{u} 时，我们反复拓展了同一个子树，导致了极大的浪费，一个点的子树可能会被这个点的所有祖先扫个遍，所以优化这个过程是我们解题的关键。

我们发现，在求 f_{u} 拓展到一个点 cur 时，我们一定会按照求 f_{cur} 的顺序拓展 cur 的子树，并且这个过程是必要的。否则进入 cur 的子树就是无意义的（赚不到钱啊），不会选择进入它。

为了方便表述，我们将求完一个点的 f 之后堆中剩下点的点集称为边界弧。因为在这个点的子树内，边界弧之上的点都被拓展过了，而边界弧之下的点都还没被拓展。至于为什么是弧，只是我在画图的时候画成了一条弧线。

这样就好办了，我们在求完一个点的 f 之后，将它的边界弧存好，在祖先拓展到它的时候我们直接调用，将拓展至边界弧的过程直接跳过。具体的，我们把存好的边界弧直接合并到现在维护的堆中即可。这个过程需要一个可并堆。由于跳过了这个过程，所以我们还要对每个点维护一个 got_{u} 表示 u 节点拓展到边界弧所赚到的钱数，以此来更新我们维护的 now。

至于可并堆的合并，我们可以采用启发式合并。

简单分析一下复杂度，边界弧只会向下推不会向上推，所以每个点只会被边界弧扫到一次，这个过程是 O(n\log{n}) 的，复杂度瓶颈在于可并堆合并，理论上界为 O(n\log^{2}{n}) 而且似乎不怎么能跑满，通过本题毫无压力。

那么我们就愉快地做完了这一题。本人比较懒，所以从 xiezheyuan 巨佬那要到了 pbds 可并堆来用。

#include <iostream>
#include <bits/extc++.h>

using namespace std;

#define LL long long
#define heap __gnu_pbds::priority_queue<int, cmp, __gnu_pbds::pairing_heap_tag>

const int N = 3e5 + 5;

int n;
int h[N], to[N], nxt[N], tot;
LL f[N], got[N], p[N], s;

struct cmp {
    bool operator () (int x, int y) {
        return f[x] > f[y];
    }
};

heap q[N];

void add(int u, int v) {
    nxt[++tot] = h[u], to[h[u] = tot] = v;
}

void push(int u) {
    LL now = 0;

    f[u] = 0;
    q[u].push(u);

    while(!q[u].empty()) {
        int cur = q[u].top();

        q[u].pop();

        if(f[cur] == 2e18) {
            break;
        }

        if(now < f[cur]) {
            f[u] += f[cur] - now;
            now = f[cur];
        }

        if(cur == u) {
            now += p[cur];
            for(int i = h[cur]; i; i = nxt[i]) {
                int v = to[i];
                q[u].push(v);
            }
        } else {
            now += got[cur];

            if(q[u].size() < q[cur].size()) {
                q[u].swap(q[cur]);
            }

            q[u].join(q[cur]);
        }

        if(now > f[u]) {
            got[u] = now - f[u];
            return ;
        }
    }

    f[u] = 2e18;
}

void dfs(int u) {
    for(int i = h[u]; i; i = nxt[i]) {
        int v = to[i];

        dfs(v);
    }

    push(u);
}

void work() {
    LL now = s;
    heap node;

    node.push(1);

    while(!node.empty()) {
        int u = node.top();

        node.pop();

        if(now < f[u]) {
            break;
        }

        now += p[u];

        for(int i = h[u]; i; i = nxt[i]) {
            int v = to[i];
            node.push(v);
        }
    }

    cout << now - s << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> s;

    for(int i = 1; i <= n; i++) {
        int fa;

        cin >> p[i + 1] >> fa;
        add(fa + 1, i + 1);
    }

    dfs(1);
    work();
}