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