Problem : 334 - 樹之國 II

Problem Statistics

Solved Member: 20　　Submission: 37　　User Tried: 20

Statement:

傳說中有一個遙遠的國度叫做樹之國。它之所以會被取名為樹之國，是因為這個國家裡面的都市和連接都市的道路會組成一棵樹，亦即不會有環的情況產生。這個國家一共有 n 個都市和 n-1 條道路。

今天新國王想要在其中一個都市設置皇宮，該都市必須滿足以下條件:

1. 該都市必需有兩條對外道路
2. 每條對外道路連接的子樹為一個行政區，我們定義他的偏僻度為行政區的都市中離皇宮最遠的距離

為了避免最偏僻的行政區不滿而暴動，國王希望最偏僻及第二偏僻的兩個行政區偏僻度相差最小。請幫國王算出最佳的首都位置。

Input:Output:

第一行有一個正整數 N 表示樹之國有幾個都市。
第 2 到第 N 行描述樹之國的道路關係，每行依序有 A, B, D 三個正整數表示都市 A 及都市 B 中有一條距離為 D 的道路。

$3 \le N \le 100000$
$1 \le D \le 1000$
保證最佳首都只會有一個

60% 的測試資料中：$N \le 1000$

輸出一個正整數表示最佳首都的編號。

Sample Input:Sample Output:

7
2 3 20
3 4 18
3 5 10
5 7 30
5 1 10
1 6 15

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	262144kb
1	500ms	262144kb	10
2	500ms	262144kb	10
3	500ms	262144kb	10
4	500ms	262144kb	10
5	500ms	262144kb	10
6	500ms	262144kb	10
7	500ms	262144kb	10
8	500ms	262144kb	10
9	500ms	262144kb	10
10	500ms	262144kb	10