DFS 游戏

时间限制：2s
空间限制：512MB

题目描述

高桥君和青木君在一棵有 $n$ 个顶点的有根树上进行游戏。根为顶点 $1$，每个顶点初始有一枚硬币，棋子初始位于顶点 $1$。高桥君先手，双方轮流操作。

若棋子所在顶点还有硬币，当前玩家取得这枚硬币并结束回合；否则，若当前顶点存在仍有硬币的子节点，当前玩家选择一个这样的子节点并把棋子移过去；若不存在这样的子节点，则在根处结束游戏，在非根处把棋子移到父节点。双方都希望最大化自己取得的硬币数，求高桥君最终取得的硬币数。

输入格式

第一行包含整数 $n$，第二行包含 $p_2,p_3,\ldots,p_n$，其中 $p_v$ 为顶点 $v$ 的父节点。

输出格式

输出高桥君在双方都采用最优策略时取得的硬币数。

样例输入 1

10
1 2 3 4 5 6 7 8 9

样例输出 1

10

样例输入 2

5
1 2 3 1

样例输出 2

2

样例输入 3

10
1 1 3 1 3 6 7 6 6

样例输出 3

5

数据范围

• $2\le n\le10^5$；
• $1\le p_v<v$。