購物中心選位置 (AP325 P-8-3)

有 \(n\) 個小村莊以 \(0 \sim n-1\) 編號，其中編號 \(0\) 的是市政府所在地，這些村莊以 \(n-1\) 條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任一個村莊 \(i\) 都可以經由這些道路到達市政府所在的 \(0\) 號村莊，所以也可以到達任何其他村莊，而且由村莊 \(i\) 往市政府會經過的第一站村莊是 \(p(i)\)。現在某大集團希望選其中一個村莊來蓋一個購物中心，選址的判斷方式是購物中心到所有村莊的距離總和要越小越好，請你幫忙計算哪一個村莊是最好的位置，到各村莊的距離總和最小是多少。

輸入格式

第一行是正整數 \(n\)，村莊以 \(0 \sim n-1\) 編號。接下來有 \(n-1\) 行是道路的資料，\(i\) 由 \(1\) 到 \(n-1\)，第 \(i\) 行有 \(2\) 個整數 \(p(i)\) 與 \(w(i)\)，代表 \(i\) 往 \(0\) 號村莊的道路第一個會經過 \(p(i)\)，而 \(i\) 與 \(p(i)\) 之間的道路長度是 \(w(i)\)。同一行的數字以一個空白隔開。

限制

• \(2 \le n \le 10^5\)。
• \(0 \le p(i) \le n-1\)，\(p(i) \ne i\)；每條道路的長度 \(w(i)\) 是不超過 \(1000\) 的正整數。
• 保證由每個村莊都可以到達 \(0\) 號村莊。注意 \(p(i)\) 的編號不一定比 \(i\) 小。

輸出格式

第一行輸出最佳的村莊編號，如果有超過一個村莊都是最佳位置，則找離市政府最遠的那一個；第二行輸出最佳村莊到各村莊距離總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
0 5
4 1
4 4
0 2

範例輸出 1

4
14

範例輸入 2

6
0 9
0 1
2 1
5 3
3 2

範例輸出 2

3
21

範例說明

範例一：最佳位置是 \(4\) 號村莊，\(4\) 到其它村莊的距離總和是 \(14\)。

範例二：\(2\) 與 \(3\) 到其它村莊的距離總和都是最小的 \(21\)，而 \(3\) 離 \(0\) 的距離比 \(2\) 與 \(0\) 的距離遠。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 P-8-3，第 279 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。