e150. 戴塔國
Tags : LCA 樹壓平
Accepted rate : 9人/10人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-09-15 16:27

Content

Deta 國擁有 N 個鎮,由N-1條道路連結,每個鎮只會有唯一條道路到其他鎮,每次經過一條道路我們都必須付wi的過路費。

有一位商人mega,他想知道由A地到B地需要花費多少過路費,在每次詢問之後,最貴一條道路會神奇地減少K價錢。當然減少的價錢K大於等於過路費算是非法操作,我們應該忽略它。

Input

輸入第一行有一個正整數N,接下來會有N-1行道路idi,ui,vi,wi表示uv 之間的過路費為w 然後idi 表示道路的編號 (1 ≤ idi  n-1 且idi不會重複)

接著是一個整數 Q,代表詢問次數,接下來有Q AiBi、ki,請輸出AiBi(Ai可能等於Bi)之間的過路費並將目前過路費最貴的道路費用減少ki (如果最貴的過路費同時有許多條請修改id最小的那個)

( 1 ≤  N,ui,v≤ 100,000  1 ≤ ≤ 100,000      w≤ 200,000      ki ≤100,000  且保證答案不超過int_64範圍)

 

Output

輸出Q行,每行有一個數字,代表AB之間的過路費。

 

Sample Input #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
Sample Output #1
8
1
8
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (10%): 0.7s , <1M
公開 測資點#1 (10%): 0.7s , <1M
公開 測資點#2 (3%): 0.7s , <10M
公開 測資點#3 (3%): 0.7s , <10M
公開 測資點#4 (4%): 0.7s , <10M
公開 測資點#5 (10%): 0.7s , <1M
公開 測資點#6 (10%): 0.7s , <1M
公開 測資點#7 (6%): 0.7s , <10M
公開 測資點#8 (6%): 0.7s , <10M
公開 測資點#9 (6%): 0.7s , <10M
公開 測資點#10 (6%): 0.7s , <10M
公開 測資點#11 (6%): 0.7s , <10M
公開 測資點#12 (6%): 0.7s , <10M
公開 測資點#13 (7%): 0.7s , <10M
公開 測資點#14 (7%): 0.7s , <10M
Hint :

本題共有四個子題

第一子題,N ≤ 1000,Q ≤1000 解出可以獲得 20 分;

第二子題,N ≤ 100,000,Q ≤100,000 且  ki=0 。解出可以獲得 10 分;

第三子題,圖的樣子一定是一條長鏈且N ≤ 100,000,Q ≤100,000。解出可以獲得 20 分 。

第四子題,無額外限制。解出可以獲得 50 分。

Tags:
LCA 樹壓平
出處:
detaomega [管理者: mmi366127 (unknown) ]

Status Forum 排行

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