Deta 國擁有 N 個鎮,由N-1條道路連結,每個鎮只會有唯一條道路到其他鎮,每次經過一條道路我們都必須付wi的過路費。
有一位商人mega,他想知道由A地到B地需要花費多少過路費,在每次詢問之後,最貴一條道路會神奇地減少K價錢。當然減少的價錢K大於等於過路費算是非法操作,我們應該忽略它。
輸入第一行有一個正整數N,接下來會有N-1行道路idi,ui,vi,wi表示u到v 之間的過路費為w 然後idi 表示道路的編號 (1 ≤ idi ≤ n-1 且idi不會重複)
接著是一個整數 Q,代表詢問次數,接下來有Q行 Ai、Bi、ki,請輸出Ai到Bi(Ai可能等於Bi)之間的過路費並將目前過路費最貴的道路費用減少ki (如果最貴的過路費同時有許多條請修改id最小的那個)。
( 1 ≤ N,ui,vi ≤ 100,000 1 ≤ Q ≤ 100,000 wi ≤ 200,000 ki ≤100,000 且保證答案不超過int_64範圍)
輸出Q行,每行有一個數字,代表A到B之間的過路費。
5 1 1 2 8 2 1 3 8 3 1 4 8 4 1 5 8 3 1 2 7 1 2 8 1 5 7
8 1 8
本題共有四個子題
第一子題,N ≤ 1000,Q ≤1000 解出可以獲得 20 分;
第二子題,N ≤ 100,000,Q ≤100,000 且 ki=0 。解出可以獲得 10 分;
第三子題,圖的樣子一定是一條長鏈且N ≤ 100,000,Q ≤100,000。解出可以獲得 20 分 。
第四子題,無額外限制。解出可以獲得 50 分。
ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」
|