local mfl, mce, mmi = math.floor, math.ceil, math.min local SegTree = {} SegTree.updateAll = function(self) for i = self.stagenum - 1, 1, -1 do for j = 1, self.cnt[i] do self.stage[i][j] = self.stage[i + 1][j * 2 - 1] + self.stage[i + 1][j * 2] end end end SegTree.create = function(self, n) local stagenum, mul = 1, 1 self.cnt, self.stage, self.size = {1}, {{}}, {} while mul < n do mul, stagenum = mul * 2, stagenum + 1 self.cnt[stagenum], self.stage[stagenum] = mul, {} end for i = 1, stagenum do self.size[i] = self.cnt[stagenum + 1 - i] end self.stagenum = stagenum for i = 1, mul do self.stage[stagenum][i] = 0 end self:updateAll() end SegTree.getRange = function(self, right) local start_stage = 1 while right < self.size[start_stage] do start_stage = start_stage + 1 end local ret = 0 local t1, t2, t3 = {start_stage}, {1}, {right} while 0 < #t1 do local stage, l, r = t1[#t1], t2[#t1], t3[#t1] table.remove(t1) table.remove(t2) table.remove(t3) local sz = self.size[stage] if (l - 1) % sz ~= 0 then local newr = mmi(r, mce((l - 1) / sz) * sz) table.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, newr) l = newr + 1 end if sz <= r + 1 - l then ret = ret + self.stage[stage][mce(l / sz)] l = l + sz end if l <= r then table.insert(t1, stage + 1) table.insert(t2, l) table.insert(t3, r) end end return ret end SegTree.setValue = function(self, idx, value, silent) self.stage[self.stagenum][idx] = value if not silent then for i = self.stagenum - 1, 1, -1 do local dst = mce(idx / 2) local rem = dst * 4 - 1 - idx self.stage[i][dst] = self.stage[i + 1][idx] + self.stage[i + 1][rem] idx = dst end end end SegTree.new = function(n) local obj = {} setmetatable(obj, {__index = SegTree}) obj:create(n) return obj end local n = io.read("*n") local edge = {} local asked = {} local calced = {} for i = 1, n do edge[i] = {} asked[i] = false calced[i] = false end calced[1] = true for i = 2, n do local a = 1 + io.read("*n") table.insert(edge[i], a) table.insert(edge[a], i) end local st = SegTree.new(n) local tasks = {1} local ret = 0 while 0 < #tasks do local src = tasks[#tasks] table.remove(tasks) asked[src] = true if not calced[src] then calced[src] = true ret = ret + st:getRange(src - 1) end local haschild = false while 0 < #edge[src] do local dst = edge[src][#edge[src]] if not asked[dst] then st:setValue(src, 1) haschild = true table.insert(tasks, src) table.insert(tasks, dst) table.remove(edge[src]) break else table.remove(edge[src]) end end if not haschild then st:setValue(src, 0) end end print(ret)