有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的正整數。
第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個，第二行輸出最佳村莊到各村莊距離總和。
5 0 5 4 1 4 4 0 2
4 14
最佳位置是4號村莊，4到其它村莊的距離總和是14。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||