d108. Q-8-6. 樹狀圖的距離總和

內容

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

輸入說明

第一行是正整數 $ 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$ 的正整數。

輸出說明

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

範例輸入 #1

4
1 2 3
10 20 30

範例輸出 #1

範例輸入 #2

5
1 1 1 2
20 20 30 30

範例輸出 #2

測資資訊：

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

提示：

標籤:

圖論樹

出處:

AP325 [管理者：

TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」