有 n 個小村莊以 0~n-1 編號，其中編號 0 的是市政府所在地，這些村莊以 n-1 條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任一個村莊 i 都可以經由這些道路到達市政府所在的 0 號村莊，所以也可以到達任何其他村莊，而且由村莊 i 往市政府會經過的第一站村莊是 p(i)。現在某大集團希望選其中一個村莊來蓋一個購物中心，選址的判斷方式是購物中心到所有村莊的距離總和要越小越好，請你幫忙計算哪一個村莊是最好的位置，到各村莊的距離總和最小是多少。
Time limit: 1 秒
第一行是正整數 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 的正整數。
第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個，第二行輸出最佳村莊到各村莊距離總和。
範例一： 5 0 5 4 1 4 4 0 2 範例二： 6 0 9 0 1 2 1 5 3 3 2
範例一： 4 14 範例二： 3 21
範例一說明：最佳位置是 4 號村莊，4 到其它村莊的距離總和是 14。
範例二說明：2 與 3 到其它的距離總和都是最小的 21，而 3 離 0 的距離比 2 與 0 的距離遠。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||