時間限制 1000 ms ・ 記憶體限制 512 MB
題目描述
貨物由 1 號裝置進入一棵二元樹。1 至 n−1 號是切換器，n 至 2n−1 號是貨箱。每個切換器的左右出口各接一個裝置。 每件貨物通過切換器時，比較兩個出口下方全部貨箱的目前總重量，送往較輕的一側；相同時走左側。貨物抵達貨箱後留在其中並增加該箱重量，會影響後續貨物。求每件貨物的目的貨箱。
輸入格式
第一行為正整數 n、m，n ≤ 10^5，m ≤ 100。第二行依序給出 n 至 2n−1 號貨箱的非負初始重量。第三行是依進入順序排列的 m 個正貨物重量。所有初始重量與貨物重量總和不超過 10^9。 接著 n−1 行各為 p、s、t，表示切換器 p 的左、右出口分別接 s、t；1 ≤ p < n。給定的連接構成上述系統。
輸出格式
依序輸出 m 個目的貨箱編號，以空白分隔。
範例測資
範例輸入 1
4 5 0 0 0 0 5 3 4 2 1 1 2 3 2 4 5 3 6 7
範例輸出 1
4 6 7 5 5
範例輸入 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
範例輸出 2
8 7
請先登入後再提交程式碼
討論與題解
載入討論區…