题解：CF1193B Magic Tree

· · 题解

诸位大佬做法太妙了，配个图好好讲讲。

首先这是个很显然的树形 dp，设 f_{u, i} 表示在以 u 为根的子树中于不晚于 i 时刻割断 (p_u, u) 可得的最大收益，那么有如下情况：

上面两个东西取 max 即可。

然后你会发现 f_u 必然是单调不降的，所以可以把它看做若干条线段：

所以我们只需要对每条线段记录一个值表示其与上一条的差值即可（形似差分），显然它的数量是 \mathcal O (m)（即 d_u 种类数）的，用 map 存储。

也就是说，现在我们需要思考如何合并子树并转移。第一种情况直接对位加上即可，第二种则涉及区间加。合并的时候显然按秩合并可以做到 \mathcal O (n \log n)，考虑如何处理第二种情况。

记 val = w_u + \sum \limits _ {p_v = u} f_{v, d_u}，则情况二是一个与 y = val 取 max 的操作（图中描黑的是新的 f_u）：

那么记录一个当前的增量 \Delta，每次将 map 中的线段抬升，注意抬升完后一个线段会对应到多个点，需要删掉。

最后因为是 map 所以算法是双 log 的不如线段树合并优秀。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100010;
int n, m, k, d[N], w[N], p[N], rt[N], ans;
map<int, int> f[N];
void merge(int &x, int y){
    if (f[x].size() < f[y].size())swap(x, y);
    for (auto e : f[y])f[x][e.first] += e.second;
}signed main(){
    ios::sync_with_stdio(0),
    cin.tie(0), cin >> n >> m >> k;
    for (int i = 2; i <= n; i ++)cin >> p[i];
    for (int i = 1, x; i <= m; i ++)
        cin >> x, cin >> d[x] >> w[x];
    for (int i = 1; i <= n; i ++)rt[i] = i;
    for (int i = n; i; i --){
        f[rt[i]][d[i]] += w[i];
        auto it = f[rt[i]].find(d[i]);
        for (it ++; it != f[rt[i]].end(); ){
            if (it -> second > w[i]){it -> second -= w[i];break;} 
            w[i] -= it -> second, f[rt[i]].erase(it ++);
        }merge(rt[p[i]], rt[i]);
    }for (auto e : f[rt[1]])ans += e.second;return cout << ans, 0;
}