有 $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$ 不超過 $10^5$，每條道路的長度是不超過 $1000$ 的正整數。
第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個，
第二行輸出最佳村莊到各村莊距離總和。
5 0 5 4 1 4 4 0 2
4 14
6 0 9 0 1 2 1 5 3 3 2
3 21
範例一說明：最佳位置是4號村莊，4到其它村莊的距離總和是14。
範例二說明：2與3到其它的距離總和都是最小的21，而3離0的距離比2與0的距離遠。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||