AT_scpc2026_div1_d Mobilint Tensor Scheduling (ARIES)

Zye 正在使用 Mobilint 的 SDK 在 ARIES 上编写 AI 推理代码。由于 Zye 不太擅长编程，他所写的代码只能计算树形图结构。 现在，Zye 想要计算一个有 $N$ 个张量组成的有根树形计算图。树的根结点为 $1$。树中第 $i$ 个结点表示一个大小为 $w_i$ MiB 的张量。 由叶节点表示的张量称为**输入张量**，由非叶节点表示的张量称为**结果张量**。输入张量在初始状态下已经存在于内存中。初始状态下的内存使用量至多为 $M$ MiB。 要计算由结点 $i$ 表示的结果张量，必须保证所有子节点对应的张量当前都存在于内存中。在计算结点 $i$ 的结果张量时，首先会在内存中分配一个大小为 $w_i$ MiB 的结果张量。计算结束后，所有属于 $i$ 子节点的张量将被从内存中移除。 某一时刻的内存使用量定义为当前内存中存在的所有张量的大小之和。 Zye 想要选择一种计算顺序，使得计算根结点所代表张量的过程中，峰值内存使用量最小。峰值内存使用量是指在初始状态以及整个计算过程中所有时刻的最大内存使用量。 计算机的内存限制为 $M$ MiB。整个计算过程中，内存使用量始终不能超过 $M$ MiB。 请找出计算根节点所表示结果张量所需的最小峰值内存用量。

输入从标准输入给出，格式如下： > $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$ 所表示的张量。因此，内存使用量为 $2+4+3+1=10$ MiB。 例如，可以按如下顺序计算结果张量： 1. 计算结点 $4$ 的结果张量。此步骤最大内存使用量为 $10+3=13$ MiB。 2. 计算结点 $3$ 的结果张量。此步骤最大内存使用量为 $9+5=14$ MiB。 3. 计算结点 $2$ 的结果张量。此步骤最大内存使用量为 $10+4=14$ MiB。 4. 计算结点 $1$ 的结果张量。此步骤最大内存使用量为 $9+6=15$ MiB。 这种计算顺序下的峰值内存使用量为 $15$ MiB。不可能将峰值内存使用量降至 $14$ MiB 或更小，因此答案为 $15$。 ### 数据范围 - $2 \leq N \leq 200\,000$ - $M = 16\,384$ - $1 \leq w_i \leq M$ - $1 \leq p_i \leq N$ - 所给图为以 $1$ 号节点为根的树。 - 所有输入都是整数。 由 ChatGPT 5 翻译