樹狀圖的距離總和 (AP325 Q-8-6)

輸入一個樹狀圖，請計算所有點到所有點的距離總和。本題假設編號 \(1\) 是根節點。

輸入格式

第一行是正整數 \(n\)，代表點數，點以 \(1 \sim n\) 編號。第二行有 \(n-1\) 個正整數 \(p(2), p(3), \ldots, p(n)\)，依序是編號 \(2 \sim\) 編號 \(n\) 各點的 parent。第三行有 \(n-1\) 個正整數，依序代表 \(i\) 從 \(2\) 到 \(n\)，邊 \((i, p(i))\) 的長度。同一行的數字以一個空白隔開。

限制

• \(2 \le n \le 10^5\)。
• \(1 \le p(i) \le n\)，\(p(i) \ne i\)；每條邊長度是不超過 \(1000\) 的正整數。
• 保證輸入是一棵以 \(1\) 為根的樹。注意 \(p(i)\) 的編號不一定比 \(i\) 小。

輸出格式

各點到各點的距離總和。請注意 \(i\) 到 \(j\) 與 \(j\) 到 \(i\) 都要納入總和，如範例。

評分說明

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

範例輸入 1

4
1 2 3
10 20 30

範例輸出 1

400

範例輸入 2

5
1 1 1 2
20 20 30 30

範例輸出 2

880

題目來源

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