f163. 貨物分配 - 高中生程式解題系統

內容

在一個貨運站有一個自動分裝系統，
在系統中有 n-1 個分裝站（編號 1 到 n-1）和 n 個貨櫃（編號 n 到 2n-1），也就是總共有 2n-1 個節點。
對於每個分裝站，都會有左右兩個分支前往下個分裝站或貨櫃。

以下圖 n = 7 為例，圓形為分裝站，方形為貨櫃：

給定 m 個不同重量的貨物（1 ≤ m ≤ 10⁴），要依序進入這個自動分裝系統以裝進貨櫃裡，分裝規則如下：

注意：貨物一旦放入貨櫃中，會影響到後續貨物進來時的走向，並且所有貨物的總重和不超過 10⁹。

假設每個貨櫃事先都包含了若干貨物重量，請計算這 m 個貨物依序會被放入哪個貨櫃中。

輸入說明

第一行包含兩個數字 n, m（1 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10⁴），
代表一共有 n 個貨櫃與 m 個準備要放入系統中的貨物

第二行有 n 個數字，
代表第 n ∼ 2n−1 個貨櫃在開始分裝系統開始前已有的貨物重量

第三行包含 m 個數字，
代表即將放入的 m 個貨物的重量

最後有 n-1 行，每行有三個數字 a, b, c，
分別代表 a 左邊的分裝站為 b，a 右邊的分裝站為 c

所有貨物，包含已有與後來放入的 m 個貨物的總重和不超過 10⁹

輸出說明

輸出這 m 個貨物被放入的貨櫃編號，數字之間兩兩以空白為間隔。

範例輸入 #1

7 2
9 2 1 6 7 4 5
2 3
1 2 5
2 3 7
3 13 10
4 9 11
6 12 8
5 6 4

範例輸出 #1

8 12

範例輸入 #2

範例輸出 #2

4 6 7 5 5

測資資訊：

記憶體限制： 512 MB

提示：

標籤:

出處:

2020年 1月 APCS [管理者： mushroom.cs9 ... (mushroom) ]