TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

70.1% (122/174)

Submission's AC Ratio

20.3% (203/999)

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

4
0 1 1
0 2 1
0 3 1

Sample Output 1

1

Sample Input 2

8
7 0 2
0 1 8
0 5 6
6 5 10
2 4 10
3 4 18
5 4 2

Sample Output 2

30

Sample Input 3

4
0 1 1
1 2 2
3 2 3

Sample Output 3

5

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 3
1 1000 524288 65536 1 3
2 1000 524288 65536 1 3
3 1000 524288 65536 1 3
4 1000 524288 65536 1 3
5 1000 524288 65536 1 3
6 1000 524288 65536 1 3
7 1000 524288 65536 1 3
8 1000 524288 65536 1 3
9 1000 524288 65536 1 3
10 1000 524288 65536 2 3
11 1000 524288 65536 2 3
12 1000 524288 65536 2 3
13 1000 524288 65536 2 3
14 1000 524288 65536 2 3
15 1000 524288 65536 2 3
16 1000 524288 65536 2 3
17 1000 524288 65536 2 3
18 1000 524288 65536 2 3
19 1000 524288 65536 2 3
20 1000 524288 65536 3
21 1000 524288 65536 3
22 1000 524288 65536 3
23 1000 524288 65536 3
24 1000 524288 65536 3
25 1000 524288 65536 3
26 1000 524288 65536 3
27 1000 524288 65536 3
28 1000 524288 65536 3
29 1000 524288 65536 3
30 1000 524288 65536 3
31 1000 524288 65536 3
32 1000 524288 65536 3
33 1000 524288 65536 3
34 1000 524288 65536 3
35 1000 524288 65536 3
36 1000 524288 65536 3
37 1000 524288 65536 3
38 1000 524288 65536 3
39 1000 524288 65536 3