AT_scpc2026_div3_b Mobilint Tensor Scheduling (REGULUS)

Zye 正在使用 Mobilint 的 SDK 为 REGULUS 编写 AI 推理代码。由于 Zye 并不擅长编程，他编写的代码只能计算树形图。 Zye 想用这段代码计算一个有 $N$ 个张量组成的有根树状计算图。树的根为节点 $1$。树中第 $i$ 个节点代表一个大小为 $w_i$ MiB 的张量。 由叶节点表示的张量称为**输入张量**，由非叶节点表示的张量称为**结果张量**。输入张量在初始状态下已存在于内存中。初始状态下的内存占用至多为 $M$ MiB。 要计算节点 $i$ 表示的结果张量，当前必须在内存中同时存在所有子节点表示的张量。计算节点 $i$ 的结果张量时，首先需要为大小为 $w_i$ MiB 的结果张量在内存中分配空间。计算完成后，所有子节点表示的张量会从内存中移除。 某一时刻的内存占用定义为该时刻内存中所有张量大小之和。 Zye 希望通过选择合理的计算顺序，使计算根节点张量的过程中，峰值内存占用最小。峰值内存占用是指初始状态及计算过程中所有时刻的最大内存占用。 计算机的内存上限为 $M$ MiB。计算过程中，内存占用始终必须不超过 $M$ MiB。 求计算根节点结果张量时所需的最小峰值内存占用。如果无法使峰值内存占用不超过 $M$ MiB，则输出 `OOM`。

输入由标准输入给出，格式如下： > $N \ M \ w_1 \ w_2 \ \dots \ w_N \ p_2 \ p_3 \ \dots \ p_N$ 其中，$p_i$ 表示节点 $i$ 的父节点编号。

如果可以在峰值内存占用不超过 $M$ MiB 的情况下计算出根节点的结果张量，输出最小可能的峰值内存占用。 否则，输出 `OOM`。

### 样例解释 1 初始状态下，存在于内存中的张量是叶节点 $5, 6, 7, 8$ 表示的输入张量。因此，初始内存占用为 $1+1+1+1=4$ MiB。 例如，可以按如下顺序计算结果张量： 1. 计算节点 $4$ 表示的结果张量，此步最大内存占用为 $4+1=5$ MiB。 2. 计算节点 $3$ 表示的结果张量，此步最大内存占用为 $4+1=5$ MiB。 3. 计算节点 $2$ 表示的结果张量，此步最大内存占用为 $3+1=4$ MiB。 4. 计算节点 $1$ 表示的结果张量，此步最大内存占用为 $2+1=3$ MiB。 该计算顺序的峰值内存占用为 $5$ MiB。不可能使峰值内存占用不超过 $4$ MiB，因此答案为 $5$。 ### 数据范围 - $2 \leq N \leq 5000$ - $M = 8192$ - $w_i = 1$ - $1 \leq p_i \leq N$ - 给定的图是一棵以节点 $1$ 为根的有根树。 - 所有输入均为整数。 由 ChatGPT 5 翻译