CF1099F Cookies

Mitya 和 Vasya 正在玩一个有趣的游戏。他们有一棵有根树，这棵树有 $n$ 个顶点，顶点编号从 $1$ 到 $n$。根节点的编号为 $1$。对于每个 $i \ge 2$ 的顶点 $i$，它有一个父节点 $p_i$，顶点 $i$ 被称为顶点 $p_i$ 的子节点。 树上的每个顶点都有一些饼干：在顶点 $i$ 上有 $x_i$ 块饼干。在顶点 $i$ 吃一块饼干需要恰好 $t_i$ 的时间。树上还有一个芯片，最初位于树根。将芯片沿着连接顶点 $i$ 与其父节点的边移动，需要花费 $l_i$ 的时间。 Mitya 和 Vasya 轮流进行游戏，Mitya 先手。 - Mitya 可以将芯片从当前位置移动到它的某个子节点。 - Vasya 可以从芯片当前位置到其某个子节点的边中，移除一条边。Vasya 也可以选择跳过这回合。 Mitya 可以在自己的任意回合选择停止游戏。一旦他停止游戏，他会将芯片沿着路径返回到根节点，并在沿途的顶点吃掉一些饼干。Mitya 可以自行决定在每个经过的顶点吃多少块饼干。下行、上行和吃饼干所花费的总时间不能超过 $T$。请注意，游戏结束时芯片必须回到树根：Mitya 不能将芯片留在其他顶点，即使他已经吃够了饼干——他必须将芯片带回根节点（每次从顶点 $v$ 移动到其父节点都需要 $l_v$ 的时间）。 无论 Vasya 如何操作，请你求出 Mitya 最多能吃到多少块饼干。

第一行包含两个整数 $n$ 和 $T$，分别表示树的顶点数和 Mitya 完成任务的总时间（$2\le n \le 10^5$，$1\le T\le10^{18}$）。 第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$，表示每个顶点上的饼干数量（$1\le x_i\le10^6$）。第三行包含 $n$ 个整数 $t_1, t_2, \ldots, t_n$，表示在每个顶点吃一块饼干所需的时间（$1\le t_i\le10^6$）。 接下来的 $n-1$ 行描述这棵树。对于每个 $i$ 从 $2$ 到 $n$，第 $i$ 行包含两个整数 $p_i$ 和 $l_i$，其中 $p_i$ 表示顶点 $i$ 的父节点，$l_i$ 表示将芯片从顶点 $i$ 移动到其父节点所需的时间（$1\le p_i < i$，$0\le l_i \le 10^9$）。

输出一个整数，表示无论 Vasya 如何操作，Mitya 最多能吃到多少块饼干。

在第一个样例测试中，Mitya 可以先将芯片移动到顶点 $2$。无论 Vasya 如何操作，Mitya 至少都能吃到 $11$ 块饼干。下面是详细的操作过程： 1. Mitya 将芯片移动到顶点 $2$。 2. Vasya 移除了与顶点 $4$ 相连的边。 3. Mitya 将芯片移动到顶点 $5$。 4. 由于顶点 $5$ 没有子节点，Vasya 不移除任何边。 5. Mitya 停止游戏，并将芯片带回根节点，在沿途吃掉饼干（在顶点 $5$ 吃 $7$ 块，在顶点 $2$ 吃 $3$ 块，在顶点 $1$ 吃 $1$ 块）。 Mitya 下行花费 $1+0$ 时间，上行花费 $0+1$ 时间，在顶点 $5$ 吃 $7$ 块饼干花费 $7\times 2$ 时间，在顶点 $2$ 吃 $3$ 块饼干花费 $3\times 3$ 时间，在顶点 $1$ 吃 $1$ 块饼干花费 $1\times 1$ 时间。总时间为 $1+0+0+1+7\times 2+3\times 3+1\times 1=26$。 由 ChatGPT 4.1 翻译