a223. Q_8_6 樹狀圖的距離總和

Content

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

Input

第一行是正整數 $n$，代表點數，點以 $1\sim n$編號，

第二行有 $n-1$ 個正整數， $p(2), p(3), …,p(n)$ ，依序是編號 $2 \sim n$各點的parent，

第三行有 $n-1$ 個正整數，依序代表 $i$ 從 $2$ 到 $n$，邊 $(i,p(i))$ 的長度。$n$ 不超過 $10^5$，每條邊長度是不超過 $1000$ 的正整數。

Output

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

Sample Input #1

4
1 2 3
10 20 30

Sample Output #1

Sample Input #2

5
1 1 1 2
20 20 30 30

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (1%): 1.0s , <1K
公開測資點#1 (19%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <1K
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <1M
公開測資點#5 (20%): 1.0s , <1M

Hint ：

請看看P-8-3題中計算median到所有點的距離和所使用的方法。

Tags:

ch8

出處:

Prof.Wu [管理者： zero(管理員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」