题解：CF1193B Magic Tree

· · 题解

纵使数据结构虐我千百遍，我仍爱她如初恋。

一直想自己独立写线段树优化 DP，磕了好几个小时结果因为实现方式太劣，频频 TLE，看了其它题解才调出来。

想想朴素的 DP 怎么写。设 f_{u,i} 表示节点 u 到第 i 天时可以获得的最大收益。那么，他可以将与其子节点相连的边割断，然后计算其子节点的价值，即

f_{u,i} \gets \sum_{v \in son(u)} \max_{j=1}^i f_{v,j}.

同时，如果他有果实，那么他可以在 d_u 时将他与父节点相连的边割断，获得 w_u 的价值，即

f_{u,d_u} \gets f_{u, d_u} + w_u.

发现这个 \max 难以处理，我们对其进行一个前缀 \max，记 g_{u,i} = \max_{j=1}^i f_{u,j}，然后就得到了朴素的 DP。

思考如何优化，发现这是一个线段树合并优化 DP 的典型例子。对于每一个点建立一个动态开点线段树，其中，节点 [u,l,r] 表示管辖范围内的 g 的最大值或最小值，然后正常合并即可。

这里给出两个不错的 trick：

  1. 为减小空间复杂度，我们建立一个回收池存储用过但已经没用的点，因为对于 u，他的子树内的非儿子节点都是没有用的。
  2. 直接维护会导致 TLE，我们发现可以记录一个点的最大值和最小值，如果最大值和最小值相同，那么可以直接将其视为一个节点，不用下传，并删除其左右儿子。同时，在第二个转移方程时进行前缀 \max 且整段的最值小于该值的时候，我们只需要将整段删除儿子节点，有需要的时候在加入即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, s, t) for (int i = s; i <= (int)t; i++)
#define pre(i, s, t) for (int i = s; i >= (int)t; i--)
#define mid (((l) + (r)) >> 1)
const int N = 1e5 + 2, M = N * 40;
int n, m, k, d[N], w[N], rt[N], stk[M], top; // stk 为回收池
int ls[M], rs[M], mx[M], mn[M], ad[M], idx;
vector<int> g[N];
inline void add(int u, int v) { if (u) ad[u] += v, mx[u] += v, mn[u] += v; }
inline void reuse(int &x) { if (x) ls[x] = rs[x] = mn[x] = mx[x] = ad[x] = 0, stk[++top] = x, x = 0; }
inline int nwn() { return (top ? stk[top--] : ++idx); }
inline bool chk(int u) { return mx[u] == mn[u]; }
inline void pushdw(int u) { if (ad[u]) add(ls[u], ad[u]), add(rs[u], ad[u]), ad[u] = 0; }
inline void pushup(int u) {
    mx[u] = max(mx[ls[u]], mx[rs[u]]);
    mn[u] = min(mn[ls[u]], mn[rs[u]]);
    if (chk(u)) reuse(ls[u]), reuse(rs[u]);
}
void upd(int u, int l, int r, int ql, int qr, int v) {
    if (mn[u] >= v) return;
    if (ql <= l && r <= qr && mx[u] <= v) {
        mx[u] = mn[u] = v, ad[u] = 0;
        return reuse(ls[u]), reuse(rs[u]);
    }
    pushdw(u);
    if (chk(u)) {
        ls[u] = nwn(), mx[ls[u]] = mn[ls[u]] = mx[u];
        rs[u] = nwn(), mx[rs[u]] = mn[rs[u]] = mx[u];
    }
    if (ql <= mid) upd(ls[u], l, mid, ql, qr, v);
    if (qr > mid) upd(rs[u], mid + 1, r, ql, qr, v);
    pushup(u);
}
int qry(int u, int l, int r, int p) {
    if (chk(u)) return mx[u];
    pushdw(u);
    if (p <= mid) return qry(ls[u], l, mid, p);
    return qry(rs[u], mid + 1, r, p);
}
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (chk(y)) return add(x, mx[y]), x;
    if (chk(x)) return add(y, mx[x]), y;
    pushdw(x), pushdw(y);
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    return pushup(x), x;
}
void dfs(int u) {
    rt[u] = nwn();
    for (int v : g[u]) dfs(v), rt[u] = merge(rt[u], rt[v]);
    if (w[u]) upd(rt[u], 1, k, d[u], k, qry(rt[u], 1, k, d[u]) + w[u]);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> k;
    rep(i, 2, n) { int x; cin >> x; g[x].push_back(i); }
    rep(i, 1, m) { int x; cin >> x >> d[x] >> w[x]; }
    dfs(1), cout << mx[rt[1]];
    return 0;
}
// f[u][i]<-\sum \max f[v][i]
// f[u][i == d_i] += w[i]
// 做前缀max
/*
3 2 10
1
1
2 4 1
3 9 3
*/