棕櫚島是杜拜城著名的人工島,也是世界知名的觀光勝地,島的形狀就像一棵棕櫚樹,每年都吸引
了上千萬人前往旅遊。為了促進觀光產業的發展,踢歐埃大公國也計畫建立一座人工島,叫做「樹狀
結構島」。整座島是由
異的景點。若把這些景點當成節點且道路當成邊來看的話,可以發現整個島恰是一個樹狀結構的圖。
也就是說,任兩點之間都是連通的,並且其間只存在唯一一條路徑。並且兩景點間的距離,定義為其
間路徑的長度(即該路徑上所有道路的長度總和)。
為了發展觀光產業,人工島預計要將某些道路改建成高速公路,使得這些道路串連後恰好是連接某
兩個最遠景點的路徑。然而因為經濟的動蕩,要搭建時發現預算不足,無法建立太長的高速公路,因
此踢歐埃大公國決定建立一條高速公路連結島上「次遠」的兩景點。所謂「次遠」的兩景點是指一對
景點,其間的距離為「比最遠距離小」的所有可能裡最大的。以下面的範例測試一為例,所有景點對
的距離由大至小排列為
請寫一支程式,幫助踢歐埃大公國,計算樹狀結構島上次遠的兩點距離。
輸入共
來有
且這條道路的長度為
輸出為一正整數,代表所求之次遠距離。
•
• 對所有
• 對所有
• 給定的圖為一棵樹。
本題共有三組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。
1. (
2. (
3. (
2020 TOI 入營考
testdata set by Omelet
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~9 | 19 | |
2 | 10~19 | 任意 |
34 |
3 | 0~39 | 無額外限制 | 47 |