c313: PF:終末之塔
標籤 :
通過比率 : 73% (8 人 / 11 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2017-10-29 16:45

內容 :

透過老巫婆的幫助,小風終於來到綁架者所在之塔,一進到塔內,小風只看到綁架者一人,而那人正是小風的大情敵:小元。
「果然就是你...你為甚麼綁架他?」
「因為我總是無法獲得她的芳心,我再也忍受不了,所以我決定要好好玩弄你們,哈哈哈哈哈...」
「不過倒也不是不能給你線索找到他,看到這張地圖了沒,這是整個森林所有塔的位置圖及路線。而我把他關在那裡...,如果你想要救她的話,那就請你告訴
我從這裡到那裏的路線中某段連接兩塔路長的最大值吧哈哈哈,你一定答不出來的!」
小風仔細看著這張地圖,發現這題圖非常特殊,這n個塔之間恰好被n-1條路連接著,所以其實任意兩座塔之間恰有唯一一條路線連接著。
於是小風再次透過他的預知能力得到了每一條路的路長,這麼一來得到最大值就十分簡單了。
「怎...怎麼可能竟然這麼快就被你答出來了?沒關係我再把你們換到不同的塔不斷地換這樣你就不可能短時間內得到所有答案了哈哈。」
小風這下果然被難倒了,這次他還是需要你幫助他快點得出他們之間路線的路長最大值。

輸入說明

輸入每一行有一個正整數n代表塔的數量
接下來n-1行,每一行有三個正整數x,y,d代表塔x和塔y(1<=x,y<=n)之間被一條路長為d的路連接著
接下來有一個正整數q代表詢問的數量
每一個詢問均有兩個正整數a,b(1<=a,b<=n)代表你被換到塔a而小文被換到塔b
測資點1(15%)滿足n<=10且q<=20
測資點2(15%)滿足n<=100000,q<=30000且所有的a均為1
測資點3和4(共70%)滿足n,q<=100000

輸出說明

對於每一個詢問,請輸出一個正整數代表從塔a走到塔b,小風經過所有路的路長的最大值。

範例輸入
5
1 2 7
5 2 1
4 1 2
2 3 8
3
1 3
4 2
5 3
範例輸出
8
7
8
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (15%): 1.0s , <1K
不公開 測資點#1 (15%): 1.0s , <10M
不公開 測資點#2 (35%): 1.0s , <10M
不公開 測資點#3 (35%): 1.0s , <10M
提示 :

「終於...終於找到妳了呢~ 花了我好的功夫阿」
「我一直相信...你一定會來找我的呢」
「從今以後,我再也不會讓妳離開我身邊了!!」
「我也是,今後將不會再離開你的身旁。」

p.s:題目故事純屬虛構,請勿和真實世界的人有過度的聯想。

標籤:
出處:
2017高雄市高師大附中資訊學科能力 [編輯:
ltf0501 (ltfsjl)
]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」