← 返回题目列表

AtCoder · scpc2026_div1_d

D. Mobilint 张量调度 (ARIES)

中文机器翻译题面 查看原题

表示言語

/ /

分数: 100 点

问题陈述

Zye 正在使用 Mobilint 的 SDK 编写在 ARIES 上运行的 AI 推理代码。由于Zye是一名不太擅长编码的开发人员,因此他编写的代码只能计算树形图。

使用此代码,Zye 想要计算一个有根树形计算图,其中包含 N 张量。树的根是节点 1。节点 树的 i 表示大小为的张量 w_i MiB。

由叶节点表示的张量称为 输入张量,非叶节点表示的张量称为 结果张量。输入张量在初始状态下已存在于内存中。初始状态下的内存使用量最多为 M MiB。

计算节点表示的结果张量 i,由子代表示的所有张量 i 当前必须存在于内存中。计算节点表示的结果张量时 i,首先是大小的结果张量 w_i MiB 已在内存中分配。计算完成后,由子代表示的所有张量 i 已从内存中删除。

某一时刻的内存使用量定义为该时刻内存中存在的所有张量的大小之和。

Zye 希望选择计算顺序,以便最小化计算根节点表示的张量时的峰值内存使用量。峰值内存使用量是初始状态和计算过程中所有时刻的最大内存使用量。

计算机的内存限制为 M MiB。在计算过程中,内存使用量必须始终最多为 M MiB。

找到计算根节点表示的结果张量所需的最小峰值内存使用量。

约束

  • 2 \leq N \leq 200\,000
  • M = 16\,384
  • 1 \leq w_i \leq M
  • 1 \leq p_i \leq N
  • 给定的图是具有根节点的有根树 1.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
w_1 w_2 \dots w_N
p_2 p_3 \dots p_N

在这里, p_i 表示节点的父节点 i.

输出

如果可以计算根节点表示的结果张量,使得峰值内存使用量最多为 M MiB,输出最小可能的峰值内存使用量。

否则,输出 OOM 。


示例输入 1

8 16384
6 4 5 3 2 4 3 1
1 1 2 2 4 3 3

示例输出 1

15

初始状态下,内存中存在的张量是叶子节点表示的输入张量 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.

表示言語

/ /

分数: 100 点

문제

已开发出 SDK 和 ARIES 功能,包括 AI 功能和 AI 功能。 자는 코딩을 잘 하지 못하는 개발자기 때문에 자딩을 잘 코드로는 트리 모양의 그래프만 계산할 수 있다。

자이는 이 코드로 텐서 N개로 이루어진 루트가 있는 트리 모양의 계산 그래프를 계산하려고 한다. 트리의 루트는 1번 노드이다. 트리의 i번 노드는 크기가 w_i MiB인텐서를 і리킨다。

리프 노드가 가리키는 텐서를 입력 텐서, 리프가 아닌 노드가 가리키는 텐서를 결과 텐서라고 하자. 입력 텐서는 초기 상태에서 이미 메모리에 존재한다. 초기 상태의 메모리 사용량은 M MiB 다다。

i번 노드가 가리키는 결과 텐서를 계산하려면 i의 모든 자식 노드가 가리키는 텐서가 현재 메모리에 있어야 한다. i번 노드가 가리키는 결과 텐서를 계산할 때는 먼저 크기가 w_i MiB인 결과 텐서를 메모리에 할당하고, 계산 Been 끝나면 i의 모든 자식 노드가 가리키는 텐서를 메모리에서 제거한다.

어떤 시점의 메모리 사용량은 그 시점에 메모리에 존재하는 모든 텐서 크기의 합이다.

자이는 계산 순서를 적절히 조정해 루트 노드가 가리키는 텐서를 계산할 때의 피크 메모리 사용량을 최소화하려고 한다. 피크 메모리 사용량은 초기 상태와 모든 계산 과정에서의 메모리 사용량의 최댓값이다.

사용할 컴퓨터의 메모리 한도는 M MiB 다。 계산 과정에서 메모리 사용량은 항상 M MiB ֕여야 한다.

루트 노드가 가리키는 결과 텐서를 계산하는 데 필요한 피크 메모리 사용량의 최솟값을 구해 보자.

제한

  • 2 \leq N \leq 200\,000
  • M = 16\,384
  • 1 \leq w_i \leq M
  • 1 \leq p_i \leq N
  • 주어지는 그래프는 루트가 1번인 트리이다.
  • 입력으로 주어지는 수는 모두 정수이다.

입력

입력은 다음 형식으로 표준 입력으로 주어진다.

N M
w_1 w_2 \dots w_N
p_2 p_3 \dots p_N

p_i는 i번 노드의 부모이다.

출력

피크 메모리 사용량이 M MiB 결과 텐서를 계산할 수 있다면 і한 피크 메모리 사용량의 최솟값을 출력한다.

그렇지 않다면 대신 OOM을 출력한다.


입력 예 1

8 16384
6 4 5 3 2 4 3 1
1 1 2 2 4 3 3

출력 예 1

15

초기 상태에서 메모리에 존재하는 텐서는 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이다.