d112. Q_8_6 樹狀圖的距離總和

Content

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

Input

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

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

第三行有n-1個正整數，依序代表i從2到n，邊(i,p(i))的長度。n不超過1e5，每條邊長度是不超過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

測資資訊：

記憶體限制： 256 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 [管理者： ktlai (K．我已霸榜．Tlai) ]

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