APCS202001 第4題自動分裝

在一個貨運站有一個自動分裝系統，

在系統中有 n-1 個分裝站（編號 1 到 n-1）和 n 個貨櫃（編號 n 到 2n-1），也就是總共有 2n-1 個節點。

對於每個分裝站，都會有左右兩個分支前往下個分裝站或貨櫃。

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

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

每個貨物必定由 1 號分裝站開始

對於每個分裝站，都會比較當下左右兩邊分支的貨物總重，之後選擇進入總重較輕的那一邊

若左右兩邊重量相等，則選擇左邊的分裝站

直到貨物進到貨櫃（方形處）

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

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

輸入說明

第一行包含兩個數字 n, m（1 ≤ n ≤ 10^6, 1 ≤ m ≤ 10^4），

代表一共有 n 個貨櫃與 m 個準備要放入系統中的貨物

第二行有 n 個數字，

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

第三行包含 m 個數字，

代表即將放入的 m 個貨物的重量

最後有 n-1 行，每行有三個數字 a, b, c，

分別代表 a 左邊的分裝站為 b，a 右邊的分裝站為 c

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

輸出說明

輸出這 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

4 5

0 0 0 0

5 3 4 2 1

1 2 3

2 4 5

3 6 7

輸出範例2

4 6 7 5 5

解題策略

樹狀結構，由下到上拜訪樹的拓譜搜尋，用於計算每個內部節點的重量，接著根據貨物重量由上到下決定走訪路徑。