题目描述

给定一棵 $n$ 个节点的树，需要将每个节点赋上一个权值 $i$，所有点的权值要求构成 $1\sim n$ 的排列。

一个节点称之为“好点”，要求在与其直接相连的所有点中，该点的权值为中位数（若总数为偶数个，取中间偏小的为中位数）。

比如某点权值为 $5$，与其直接相连的点的权值分别为 ：$1,2,9,6$，那么这个点是“好点”。某点权值为 $5$，与其直接相连的点的权值分别为 ：$1,2,9,6,8$，那么这个点也是“好点”。

你需要求出如何给节点们赋值，使得最后的“好点”个数最多。求出这个最多个数。

输入格式

第一行包含一个整数 $n$，表示树的节点数量；

第二行包含 $n-1$ 个整数 $\operatorname{fa}_2,\operatorname{fa}_3,\ldots,\operatorname{fa}_i$。表示节点 $i$ 的父亲（节点 $1$ 为根）

输出格式

一行一个整数，表示在所有赋值方案中能够得到的最大好点数量。

输入输出样例

3
1 1

2

样例 $\tt \#1$说明

当 $1,2,3$ 号节点分别赋值为 $2,1,3$ 时，$1,2$ 号节点都为“好点”

6
1 1 3 3 3 

5

数据范围

$10\%: n\le 10$

$20\%:n \le 20$

$50\%: n\le 2000$

另外 $10\%: fa_i = i-1$

另外 $10\%: fa_i = 1$

$100\%:2\le n\le 2\times 10^5,1\le fa_i\le i$