一、问题分析

1.1 问题描述

给定一棵 $n$ 个节点的树（根为节点 $1$），部分节点上有果实，每个果实有成熟时间 $d_j$ 和价值 $w_j$。每天可以砍断一些边，当某个节点与根断开连接时，如果该节点上的果实恰好在当天成熟，就能收获该果实。求最大总收获。

1.2 核心观察

观察1：每个节点最多被砍一次

一旦某个节点与根断开连接，它的子树中的果实只能在断开的那一天收获（如果恰好成熟）。

观察2：子树的独立性

对于某个节点 $u$，它的子树何时被砍断，与其兄弟子树无关。但需要在父节点被砍断之前砍断。

观察3：时间约束

如果在第 $d$ 天砍断节点 $u$，那么：

• $u$ 的子树必须在第 $d$ 天或之前被砍断
• $u$ 上的果实只有在 $d_u = d$ 时才能被收获

1.3 问题转化

核心思路：树形DP + 线段树合并

定义状态：

$$f[u][d] = \text{在第 } d \text{ 天砍断节点 } u \text{ 与其父节点的边时，从 } u \text{ 的子树能获得的最大果汁量} $$

状态转移：

对于节点 $u$ 的每个子节点 $v$：

• 如果在第 $d$ 天砍断 $u$，那么 $v$ 可以在 $[1, d]$ 中的任意一天被砍断
• $f[u][d]$ 需要考虑所有子树的最优组合

关键难点：如何高效合并子树信息？

二、算法设计

2.1 线段树合并

核心思想：为每个节点维护一棵动态开点线段树，线段树的每个位置 $d$ 存储 $f[u][d]$。

使用线段树合并可以在 $O(n \log k)$ 时间内完成所有DP转移。

2.2 合并策略

合并两个子树的线段树时，关键问题是：如何处理不同时间的组合？

定理1（最优子结构）：

合并节点 $u$ 的两个子树 $v_1$ 和 $v_2$ 时，对于时刻 $d$：

$$f[u][d] = \max \begin{cases} \max_{t_1 \le d} f[v_1][t_1] + f[v_2][d] \\ \max_{t_2 \le d} f[v_1][d] + f[v_2][t_2] \end{cases} $$

这意味着：

• 左子树在某个时刻 $t_1 \le d$ 被砍，右子树在时刻 $d$ 被砍
• 或者右子树在某个时刻 $t_2 \le d$ 被砍，左子树在时刻 $d$ 被砍

证明：

设左子树在 $t_1$ 砍断，右子树在 $t_2$ 砍断，如果 $\max(t_1, t_2) = d$，则可以将较早砍的那个推迟到 $d$ 时刻，不会影响收益（因为果实只在特定时刻成熟）。但实际上不能随意推迟，因为可能与节点 $u$ 自身的果实冲突。

更准确的理解：

在合并过程中，我们需要维护前缀最大值：

• premax1：左子树在 $[1, d-1]$ 中的最大值
• premax2：右子树在 $[1, d-1]$ 中的最大值

对于位置 $d$：

$$f[u][d] = \max(f[v_1][d] + \text{premax2}, f[v_2][d] + \text{premax1}) $$

2.3 懒标记优化

在合并过程中，如果某个子树的整个区间需要加上一个值，可以使用懒标记：

tree[y].val += premax1;
tree[y].lazy += premax1;

这样可以避免递归到叶子节点，提高效率。

三、代码模块详解

模块1：数据结构定义

const int N = 1e5 + 10;

int n, m, k;
int p[N], pos[N], d[N], w[N];
struct Edge {
    int to, next;
} e[N * 2];
int head[N], cnt;

变量说明：

• p[i]：节点 $i$ 的父节点
• d[i]：节点 $i$ 上果实的成熟日期（0表示无果实）
• w[i]：节点 $i$ 上果实的价值
• head[], e[]：邻接表存储树结构

模块2：线段树节点结构

struct TreeNode {
    LL val, lazy;
    int ls, rs;
} tree[N * 80];
int root[N], tot;

字段含义：

• val：该区间的最大值，即 $\max_{d \in [l,r]} f[u][d]$
• lazy：懒标记，表示该区间整体需要加上的值
• ls, rs：左右子节点的编号（动态开点）
• root[u]：节点 $u$ 对应的线段树根节点

空间分析：每个节点的线段树最多有 $O(\log k)$ 个节点（只在有值的位置开点），总空间 $O(n \log k)$。但由于合并，实际可能达到 $O(n \log k)$ 的常数倍，这里开 N * 80 是安全的。

模块3：线段树基本操作

inline void pushup(int x) {
    tree[x].val = max(tree[tree[x].ls].val, tree[tree[x].rs].val);
}

inline void pushdown(int x) {
    if (tree[x].lazy) {
        if (tree[x].ls) {
            tree[tree[x].ls].lazy += tree[x].lazy;
            tree[tree[x].ls].val += tree[x].lazy;
        }
        if (tree[x].rs) {
            tree[tree[x].rs].lazy += tree[x].lazy;
            tree[tree[x].rs].val += tree[x].lazy;
        }
        tree[x].lazy = 0;
    }
}

pushup：从子节点更新父节点的最大值。

pushdown：将懒标记下传到子节点。

模块4：查询操作

LL query(int ql, int qr, int x, int l = 1, int r = k) {
    if (ql <= l && qr >= r)
        return tree[x].val;

    LL lson = 0, rson = 0;
    pushdown(x);

    if (ql <= mid && tree[x].ls)
        lson = query(ql, qr, tree[x].ls, l, mid);

    if (qr > mid && tree[x].rs)
        rson = query(ql, qr, tree[x].rs, mid + 1, r);

    return max(lson, rson);
}

功能：查询区间 $[ql, qr]$ 的最大值。

实现要点：

• 如果当前区间完全包含在查询区间内，直接返回 val
• 否则递归查询左右子区间
• 注意判断子节点是否存在（动态开点）

时间复杂度：$O(\log k)$

模块5：单点修改

int modify(int pos, LL val, int x, int l = 1, int r = k) {
    if (!x)
        addnew(x);

    if (l == r) {
        tree[x].val = max(tree[x].val, val);
        return x;
    }

    pushdown(x);

    if (pos <= mid)
        tree[x].ls = modify(pos, val, tree[x].ls, l, mid);
    else
        tree[x].rs = modify(pos, val, tree[x].rs, mid + 1, r);

    pushup(x);
    return x;
}

功能：在位置 pos 更新值为 max(原值, val)。

实现要点：

• 动态开点：如果节点不存在，创建新节点
• 递归到叶子节点进行修改
• 回溯时更新路径上所有节点的 val

时间复杂度：$O(\log k)$

模块6：线段树合并（核心）

LL premax1, premax2;

int merge(int x, int y, int l = 1, int r = k) {
    if (!x && !y)
        return 0;
    else if (!x) {
        premax2 = max(premax2, tree[y].val);
        tree[y].val += premax1;
        tree[y].lazy += premax1;
        return y;
    } else if (!y) {
        premax1 = max(premax1, tree[x].val);
        tree[x].val += premax2;
        tree[x].lazy += premax2;
        return x;
    }

    if (l == r) {
        premax1 = max(premax1, tree[x].val);
        premax2 = max(premax2, tree[y].val);
        tree[x].val = max(tree[x].val + premax2, tree[y].val + premax1);
        return x;
    }

    pushdown(x);
    pushdown(y);
    tree[x].ls = merge(tree[x].ls, tree[y].ls, l, mid);
    tree[x].rs = merge(tree[x].rs, tree[y].rs, mid + 1, r);
    pushup(x);
    return x;
}

算法逻辑：

情况1：两个节点都为空

• 返回0（无需合并）

情况2：只有一个节点为空

• 如果 $x$ 为空：
  • 更新 premax2（记录 $y$ 子树的最大值）
  • 给 $y$ 子树整体加上 premax1（左子树的历史最大值）
  • 返回 $y$
• 如果 $y$ 为空：对称处理

情况3：叶子节点（$l = r$）

• 更新前缀最大值
• 计算合并后的值：$\max(f[x][d] + \text{premax2}, f[y][d] + \text{premax1})$

情况4：非叶子节点

• 下传懒标记
• 递归合并左右子树
• 向上更新

数学原理：

在DFS过程中从左到右合并子树。设已经合并了 $v_1, v_2, \ldots, v_{i-1}$，当前合并 $v_i$：

对于时刻 $d$，最优策略是：

• 前 $i-1$ 个子树在 $[1, d]$ 中选择最优时刻（记为 premax1）
• 第 $i$ 个子树在时刻 $d$ 砍断

或者反过来：

• 第 $i$ 个子树在 $[1, d]$ 中选择最优时刻（记为 premax2）
• 前 $i-1$ 个子树在时刻 $d$ 砍断

时间复杂度：均摊 $O(n \log k)$（线段树合并的经典结论）

模块7：树形DP主函数

void dfs(int u) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
        premax1 = premax2 = 0;
        root[u] = merge(root[u], root[v]);
    }

    if (d[u]) {
        LL tmp = query(1, d[u], root[u]);
        root[u] = modify(d[u], tmp + w[u], root[u]);
    }
}

算法流程：

步骤1：递归处理所有子节点

步骤2：合并所有子树的线段树

• 每次合并前重置 premax1 和 premax2
• 依次合并每个子树到 root[u]

步骤3：处理节点 $u$ 自身的果实

• 如果 $u$ 有果实（$d[u] > 0$）
• 查询 $[1, d[u]]$ 的最大值（子树在 $d[u]$ 天或之前被砍的最大收益）
• 在位置 $d[u]$ 更新值为 tmp + w[u]（加上 $u$ 自身的果实价值）

正确性分析：

• 合并子树时，考虑了所有可能的时间组合
• 处理自身果实时，只有在第 $d[u]$ 天砍断 $u$ 时，才能收获 $u$ 的果实
• 此时子树必须在 $d[u]$ 或之前被砍断，所以查询 $[1, d[u]]$ 的最大值

模块8：主函数

int main() {
    scanf("%d%d%d", &n, &m, &k);
    memset(head, -1, sizeof head);

    for (int i = 2; i <= n; i++) {
        scanf("%d", &p[i]);
        add(p[i], i);
    }

    for (int i = 1; i <= m; i++) {
        scanf("%d", &pos[i]);
        scanf("%d%d", &d[pos[i]], &w[pos[i]]);
    }

    dfs(1);
    LL rst = query(1, k, root[1]);
    printf("%lld", rst);

    return 0;
}

算法流程：

1. 读入树结构，构建邻接表
2. 读入果实信息，存储在对应节点
3. 从根节点开始DFS
4. 查询根节点线段树在 $[1, k]$ 的最大值（即答案）

为什么查询整个区间？

根节点不需要被砍断（它本身就在根部），所以我们可以选择在任意时刻"停止"，取所有时刻的最大值。

四、复杂度分析

4.1 时间复杂度

DFS遍历：$O(n)$

线段树操作：

• 单点修改：$O(m \log k)$（$m$ 个果实）
• 线段树合并：$O(n \log k)$（均摊）
• 区间查询：$O(m \log k)$（每个有果实的节点查询一次）

总时间复杂度：$O(n \log k)$

4.2 空间复杂度

树的存储：$O(n)$

线段树节点：$O(n \log k)$

• 每个节点的线段树最多有 $O(\log k)$ 个节点（动态开点）
• 合并过程中可能产生额外节点，但总数仍是 $O(n \log k)$ 级别

总空间复杂度：$O(n \log k)$

六、总结

6.1 核心思想

本题采用的树形DP + 线段树合并的核心思想：

1. 状态设计：$f[u][d]$ 表示在第 $d$ 天砍断节点 $u$ 时的最大收益
2. 线段树维护：用动态开点线段树存储每个节点的DP数组
3. 子树合并：通过线段树合并高效计算状态转移
4. 前缀最大值：在合并过程中维护历史最大值，处理不同时间的组合

6.3 数学洞察

定理2（最优砍边策略）：

对于每个节点，存在最优方案使得：

• 要么不砍该节点与父节点的边（永远不收获该子树）
• 要么在某个特定时刻 $d$ 砍断，此时子树中所有在 $d$ 天成熟的果实都被收获

推论：不需要考虑"部分收获"子树的情况，因为可以调整砍边时间使得收益不减。