d104. P-8-3. 購物中心選位置

內容

有 n 個小村莊以 0~n-1 編號，其中編號 0 的是市政府所在地，這些村莊以 n-1 條道路連接，每條道路都是雙向通行且連接兩個不同的村莊

已知從任一個村莊 i 都可以經由這些道路到達市政府所在的 0 號村莊，所以也可以到達任何其他村莊，而且由村莊 i 往市政府會經過的第一站村莊是 p(i)。

現在某大集團希望選其中一個村莊來蓋一個購物中心，選址的判斷方式是購物中心到所有村莊的距離總和要越小越好

請你幫忙計算哪一個村莊是最好的位置，到各村莊的距離總和最小是多少。

輸入說明

第一行是正整數 n，n>1，村莊以 0~n-1 編號

接下來有 n-1 行是道路的資料，i 由 1 到 n-1，第 i 行有 2 個整數 p(i)與 w(i)，代表 i 往 0 號村莊的道路第一個會經過 p(i)，而 i 與 p(i)之間的道路長度是 w(i)

n 不超過 1e5，每條道路的長度是不超過 1000 的正整數。

輸出說明

第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個

第二行輸出最佳村莊到各村莊距離總和。

範例輸入 #1

範例輸出 #1

4
14

範例輸入 #2

範例輸出 #2

3
21

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M

提示：

標籤:

圖論樹

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」