e150.
戴塔國
內容
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之間的過路費。
範例輸入
#1
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
範例輸出
#1
8 1 8
測資資訊：
記憶體限制：
256
MB
提示 ：
本題共有四個子題
第一子題，N ≤ 1000，Q ≤1000 解出可以獲得 20 分；
第二子題，N ≤ 100,000，Q ≤100,000 且 ki=0 。解出可以獲得 10 分；
第三子題，圖的樣子一定是一條長鏈且N ≤ 100,000，Q ≤100,000。解出可以獲得 20 分 。
第四子題，無額外限制。解出可以獲得 50 分。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||