145. Day 3 PG. 卦長的背包

0 Judge

Code: 0


卦長的背包

題目敘述

有一天卦長到了金坷拉王國,但是他不小心把隨身的魔法石背包遺失在這個王國的某個城市了,他希望在離開這個國家之前可以把背包找回來。

這個王國共有$N$($1 \leq N \leq 10^5$)個城市和$N-1$條公路,每條公路都僅連接兩個不同的城市,且保證由任意一個城市都可以藉由這些公路移動到另一個城市。為了找回背包,卦長決定由聖地牙哥(編號為$1$的城市)開始,以BFS的順序開始尋找,也就是說,他會由距離聖地牙哥最近的城市開始尋找,若有多個城市與聖地牙哥距離相等,那麼卦長會按著它們父節點城市被拜訪的順序去拜訪這些城市,如果有多個城市擁有同樣的父節點城市,那麼編號較小的城市會被卦長優先拜訪。

由於這個國家的法律禁止瞬間移動,因此卦長在拜訪這些城市的時候只能乖乖的搭車,而車費的計算方式為經過的公路數量,例如從柏林移動到法蘭克福需要經過$3$條不同的公路,那麼就需要付$3$元的車費。

由於卦長正為了他能否順利找到背包而非常焦慮,因此他希望你能幫他計算最多可能需要花費的車錢。

輸入說明

每筆測資的第一行都有一個正整數$N$,代表這個國家裡城市的數量。在第二行中有$N-1$個數字$p_2$, $p_3$, $\cdots$, $p_N$,代表節點$i$的父節點城市編號。

輸出說明

請印出卦長最多可能需要的車費。

範例輸入 1

4
1 1 2

範例輸出 1

6

範例輸入 2

4
1 1 3

範例輸出 2

4

範例輸入 3

11
1 1 3 3 2 4 1 3 2 9

範例輸出 3

25

Judge Setting

run-time limit: 1000 ms
memory limit: 6553500 byte
測資數量: 0