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