某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統,經過一些切換器的轉送後,會被輸送到 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 個貨物分別會被送到哪一個貨箱。
第一行為兩個正整數n 和m,其中n ≤ 1e5且m ≤ 100。
第二行有n 個非負整數,依序是編號為n ~ 2n–1各個貨箱初始的重量。
第三行是m個正整數,代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過1e9。
第四行開始有n–1行,這些是系統架構的資訊:每一行有三個整數p、s與t,代表裝置p的左右出口分別接到裝置s與t,其中p一定是一個切換器的編號(1 ≤ p < n)。同一行數字之間以空白間隔。
輸出一行有m個整數,依序代表接下來進入系統的m個貨物所進入到的貨箱編號,數字之間以一個空白間隔。
範例一:輸入 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
範例一:正確輸出 4 6 7 5 5 範例二:正確輸出 8 7
範例二的架構即是題目中的圖。
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |