a265. 202001_4 貨物分配

Content

某工程公司設計了一個自動分裝的系統。貨物會一個一個的被送進此系統，經過一些切換器的轉送後，會被輸送到 $n$ 個貨箱。

系統有 $(n - 1)$ 個切換器與 $n$ 個貨箱。每個切換器有一個入口以及左右兩個出口，切換器的出口會接到其他切換器或是連接到貨箱，貨箱則只有入口。

下圖是一個 $n = 7$ 的例子，圓代表切換器，方形代表貨箱，請注意編號 $1 \sim (n - 1)$ 的裝置是切換器，貨箱編號是 $n \sim (2 n - 1)$ ，且貨物入口一定是 $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$ 個貨物分別會被送到哪一個貨箱。

Input

第一行為兩個正整數 $n$ 和 $m$ ，其中 $n \leq 10^{5}$ 且 $m \leq 100$ 。

第二行有 $n$ 個非負整數，依序是編號為 $n \sim (2 n - 1)$ 各個貨箱初始的重量。

第三行是 $m$ 個正整數，代表接下來依序進入的貨物重量。全部貨箱初始的重量與貨物重量總和不會超過 $10^{9}$ 。

第四行開始有 $(n - 1)$ 行，這些是系統架構的資訊：每一行有三個整數 $p$ 、 $s$ 與 $t$ ，代表裝置 $p$ 的左右出口分別接到裝置 $s$ 與 $t$ ，其中 $p$ 一定是一個切換器的編號 $(1 \leq p < n)$ 。同一行數字之間以空白間隔。

本題包含三個子題組，每個子題組配分如下：

第 1 子題組 20 分： $n \leq 10$ ， $s = 2 p$ ， $t = 2 p + 1$ ，所有貨箱初始重量為 $0$ 。
第 2 子題組 30 分： $n \leq 1000$ ， $s = 2 p$ ， $t = 2 p + 1$ 。
第 3 子題組 50 分：無其他限制。

Output

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

Sample Input #1

Sample Output #1

4 6 7 5 5

Sample Input #2

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 #2

8 7

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 0.5s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1K
公開測資點#4 (5%): 0.5s , <1M
公開測資點#5 (5%): 0.5s , <1M
公開測資點#6 (5%): 0.5s , <1M
公開測資點#7 (5%): 0.5s , <1M
公開測資點#8 (5%): 0.5s , <1M
公開測資點#9 (5%): 0.5s , <1M
公開測資點#10 (5%): 0.5s , <10M
公開測資點#11 (5%): 0.5s , <10M
公開測資點#12 (5%): 0.5s , <10M
公開測資點#13 (5%): 0.5s , <10M
公開測資點#14 (5%): 0.5s , <10M
公開測資點#15 (5%): 0.5s , <10M
公開測資點#16 (5%): 0.5s , <10M
公開測資點#17 (5%): 0.5s , <10M
公開測資點#18 (5%): 0.5s , <10M
公開測資點#19 (5%): 0.5s , <10M

Hint ：

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

Tags:

出處:

2020年1月 APCS 演算法海牛 [管理者： zero(管理員) ]

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