e126. P-8-5. 自動分裝 (APCS202002) - 花中程式設計挑戰系統

Content

某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統，經過一些切換器的轉送後，會被輸送到 n 個貨箱。系統有 n–1 個切換器與 n 個貨箱。每個切換器有一個入口以及左右兩個出口，切換器的出口會接到其他切換器或是連接到貨箱，貨箱則只有入口。下圖是一個 n=7 的例子，圓代表切換器，方形代表貨箱，請注意編號 1 ~ n–1 的裝置是切換器，貨箱編號是 n ~ 2n–1，且貨物入口一定是 1 號切換器的入口。

每一個切換器會分別記錄左右兩個出口所通往貨箱的總重量，當貨物進入此切換器時，切換器會將貨物轉送到「貨箱總重量比較輕的那個出口」，如果兩邊一樣重，則送往左邊。以上圖的例子來說，假設每一個貨箱目前的重量如各矩形下方的標示，下一個到達的貨物的運送過程如下：一號切換器左邊出口是連到 {13, 10, 7} 三個貨箱，目前總重 5+6+9=20；右邊出口連到的是 {12, 8, 11, 9} 四個貨箱，目前總重 7+2+8+1=18，因此貨物會由右邊出口送到 5 號切換器。5 號切換器的左邊與右邊的貨箱總重是一樣的（7+2=8+1），因此貨物由左出口送至 6 號切換器。最後， 6 號切換器將貨物送到 8 號貨箱（7>2)。貨物進入貨箱後就存放在該貨箱，該貨物的重量就會加入該貨箱的總重，因此可能影響下一個貨物的運送路徑。

輸入此系統的連接架構與貨箱目前的重量，以及接下來依序進入的 m 個貨物的重量，請計算這 m 個貨物分別會被送到哪一個貨箱。

Time limit: 1 秒

Input

第一行為兩個正整數 n 和 m，其中 n <= 1e5 且 m <= 100。第二行有 n 個非負整數，依序是編號為 n ~ 2n–1 各個貨箱初始的重量。第三行是 m 個正整數，代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過10e9。第四行開始有 n–1 行，這些是系統架構的資訊：每一行有三個整數 p、s 與 t，代表裝置 p 的左右出口分別接到裝置 s 與 t，其中 p 一定是一個切換器的編號(1 <= p < n)。同一行數字之間以空白間隔。

Output

輸出一行有 m 個整數，依序代表接下來進入系統的 m 個貨物所進入到的貨箱編號，數字之間以一個空白間隔。

Sample Input

範例一：
4 5
0 0 0 0
5 3 4 2 1
1 2 3
2 4 5
3 6 7

範例二：
7 2
9 2 1 6 8 7 5
2 3
1 2 5
2 3 7
3 13 10
4 11 9
6 12 8
5 6 4

Sample Output

範例一：
4 6 7 5 5

範例二：
8 7

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

範例二的架構即是題目中的圖。

Tags:

二元樹

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」