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$的父節點城市編號。
請印出卦長最多可能需要的車費。
4
1 1 2
6
4
1 1 3
4
11
1 1 3 3 2 4 1 3 2 9
25