AT_scpc2026_div2_a Mobilint Tensor Scheduling (REGULUS)

#### 表示言語 / / ザイは Mobilint の SDK を用いて，REGULUS 上で実行する AI 推論コードを書こうとしています．ザイはコーディングがあまり得意でない開発者なので，ザイが書いたコードでは木状のグラフしか計算できません． ザイはこのコードで， $ N $ 個のテンソルからなる根付き木状の計算グラフを計算します．木の根は頂点 $ 1 $ です．木の頂点 $ i $ は，サイズが $ w_i $ MiB であるテンソルを表します． 葉が表すテンソルを**入力テンソル**，葉でない頂点が表すテンソルを**結果テンソル**と呼びます．入力テンソルは初期状態ですでにメモリ上に存在します．初期状態でのメモリ使用量は $ M $ MiB 以下です． 頂点 $ i $ が表す結果テンソルを計算するためには， $ i $ のすべての子が表すテンソルが現在メモリ上に存在している必要があります．頂点 $ i $ が表す結果テンソルを計算するときは，まずサイズ $ w_i $ MiB の結果テンソルをメモリ上に確保します．その計算が完了した直後に， $ i $ のすべての子が表すテンソルをメモリから削除します． ある時点でのメモリ使用量を，その時点でメモリ上に存在するすべてのテンソルのサイズの総和と定義します． ザイは計算順序を適切に選ぶことで，根が表すテンソルを計算するときのピークメモリ使用量を最小化したいです．ピークメモリ使用量とは，初期状態および計算過程のすべての時点におけるメモリ使用量の最大値です． 使用するコンピュータのメモリ上限は $ 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` を出力する．

由 ChatGPT 5 翻译