[题解] P6847 [CEOI2019] Magic Tree

Yansuan_HCl · 2022-08-24 22:39:07 · 题解

写篇题解纪念一下我 \color{red}{-17} 的光辉提交以及三个假算法。顺便抢了个最优解。

题意简述

每天你可以砍下树上的某些边，然后当天与 1 节点不再联通的果实如果恰好在当天成熟，则能够收获该果实的果汁。

求最大能收获的果汁量。

题解

首先需要想到一个维度含有时间的暴力 dp.

设 f_u(t) 表示在第 t 天砍断 (u,\mathrm{fa}_u) 的最大收益，则有：

暴力转移可以做到 O(n^3)。

设 g_u(t)=\min_{i=1}^tf_u(t)，则可以把上面的转移优化到 O(n^2)。不过同时存在 f 和 g 并不很雅观，而且难以进一步优化。

试着直接转移 g，则可以得到：

这样，则可以比较方便地使用数据结构维护。这里使用线段树合并。

对于操作 1，直接合并即可。操作 2 的区间取 \max 则不好处理。一种暴力的做法是对于区间打取 \max 的 tag, 合并的时候暴力下传（需要新建点）。但是这样做时间复杂度是错的。

还有一种经典做法是，把取 \max 的区间分解为一些最大值小于 \max 的区间，再把这些区间推平。本题就可以这样做！为什么复杂度是对的呢？此时不妨回顾一下转移的式子。所有的操作 2 中，被取 \max 的都是一段后缀。因此，f_u(t) 关于 t 单调不降。这说明我们只需要推平一段区间。

此外，想要时间复杂度是正确的，就要求不能下传标记。只有标记永久化的线段树满足这个条件。这要求信息是可叠加的。标记永久化的区间加线段树满足这个条件，尝试用它维护区间推平。

区间推为 0，可以用删除一个子树实现。之后再把这个区间加上 \max 即可。

代码

const int N = 100005;
int n, m, k;
// 设 f[u][t] 为在第 t 天割掉 u, u 子树内最大收益。
// 若在第 t 天割掉 u, 则子树内所有割的操作只能在第 [1..t] 天完成

// 施加 u 的限制:
// f[u][d[u]]=w[u]+\sum{g[v][d[u]]}
// g[u][i]=sum{g[u][i]+g[v][i]}
// g[u][d[u]..k] \gets w[u]+\sum{g[v][d[u]]}

struct Node { ll mn, mx, tag; int ls, rs; } tr[N << 6];
#define mid ((l + r) >> 1)
#define LS(p) tr[p].ls
#define RS(p) tr[p].rs
#define TAG(p) tr[p].tag
#define N(p) tr[p].mn
#define X(p) tr[p].mx

int trash[N << 6], tp, ap;
#define alloc() (tp ? trash[tp--] : ++ap);
#define del(p) if (p) { trash[++tp] = p; p = LS(p) = RS(p) = X(p) = TAG(p) = N(p) = 0; }

// 标记永久化线段树
// 支持区间 min max, 区间推平为 0, 区间加
// 加法是典型的可加信息。
#define maintain(p) { \
    N(p) = min(N(LS(p)), N(RS(p))) + TAG(p); \
    X(p) = max(X(LS(p)), X(RS(p))) + TAG(p); \
}
void merge(int &p, int &q, int l = 1, int r = k) {
    if (!p || !q) { p = p | q; return; }
    if (l == r) {
        TAG(p) += TAG(q);
        X(p) = N(p) = TAG(p);
        del(q);
        return;
    }
    TAG(p) += TAG(q);
    merge(LS(p), LS(q), l, mid);
    merge(RS(p), RS(q), mid + 1, r);
    del(q);
    maintain(p);
}
// [b, e] 删除并加上 v
// 其中 f[e]<=v
void cover(int b, ll v, int &p, int l = 1, int r = k) {
    if (!p) p = alloc();
    if (b <= l) {
        if (X(p) <= v) {
            del(LS(p)); del(RS(p));
            TAG(p) = X(p) = N(p) = v;
        } else {
            v -= TAG(p);
            if (N(LS(p)) <= v)
                cover(b, v, LS(p), l, mid);
            if (N(RS(p)) <= v)
                cover(b, v, RS(p), mid + 1, r);
            maintain(p);
        }
        return;
    }
    v -= TAG(p);
    if (b <= mid) cover(b, v, LS(p), l, mid);
    cover(b, v, RS(p), mid + 1, r);
    maintain(p);
}
ll query(int x, int p, int l = 1, int r = k) {
    if (!p) return 0;
    if (l == r) return TAG(p);
    return TAG(p) + ((x <= mid) ? query(x, LS(p), l, mid) : query(x, RS(p), mid + 1, r));
}

int fa[N], root[N];
int d[N]; ll w[N];

int main() {
    rd(n); rd(m); rd(k);
    U (i, 2, n) rd(fa[i]);
    U (i, 1, m) {
        int u, td; ll tw;
        rd(u); rd(td); rd(tw);
        d[u] = td;
        w[u] = tw;
    }

    D (u, n, 2) {
        if (d[u]) cover(d[u], w[u] + query(d[u], root[u]), root[u]);
        merge(root[fa[u]], root[u]);
    }

    ll f = 0;
    U (i, 1, k) f = max(f, query(i, root[1]));
    printf("%lld", f);
}

几种错误解法

贪心

按 d 从小到大加入，若 w_u > \sum_{1\to u} 则把这些点删掉。

如果一个点下面有很多 w 较小但是 \sum w 较大的点就寄了。

不含时间的 dp

分为砍下 u 和不砍下 u 两类，在上方减去贡献。

这样无法处理不摘取 u 但子树内对时间有限制的情况。

暴力 pushdown

若对一棵满树进行 2 操作，则复杂度退化为 O(n)。满树是容易构造的。

这些错误例我全写过。