Peculiar apple-tree

题意翻译

从前有一只名为 NaCly_Fish 的神鱼，她有一棵苹果树。 有一天苹果熟了，每个点都有一个苹果。神鱼用魔法让苹果从树上掉了下来。 每一秒，不在根上的苹果会掉到它的父节点上。在根上的苹果会被神鱼吃掉。 如果某一个点上有不小于 $2$ 个苹果，那么它们会两两抵消。即：$x$ 个苹果会变成 $x \bmod 2$ 个。 神鱼 NaCly_Fish 想知道，她能吃到几个苹果。

题目描述

In Arcady's garden there grows a peculiar apple-tree that fruits one time per year. Its peculiarity can be explained in following way: there are $ n $ inflorescences, numbered from $ 1 $ to $ n $ . Inflorescence number $ 1 $ is situated near base of tree and any other inflorescence with number $ i $ ( $ i>1 $ ) is situated at the top of branch, which bottom is $ p_{i} $ -th inflorescence and $ p_{i}<i $ . Once tree starts fruiting, there appears exactly one apple in each inflorescence. The same moment as apples appear, they start to roll down along branches to the very base of tree. Each second all apples, except ones in first inflorescence simultaneously roll down one branch closer to tree base, e.g. apple in $ a $ -th inflorescence gets to $ p_{a} $ -th inflorescence. Apples that end up in first inflorescence are gathered by Arcady in exactly the same moment. Second peculiarity of this tree is that once two apples are in same inflorescence they annihilate. This happens with each pair of apples, e.g. if there are $ 5 $ apples in same inflorescence in same time, only one will not be annihilated and if there are $ 8 $ apples, all apples will be annihilated. Thus, there can be no more than one apple in each inflorescence in each moment of time. Help Arcady with counting number of apples he will be able to collect from first inflorescence during one harvest.

输入输出格式

输入格式

First line of input contains single integer number $ n $ ( $ 2<=n<=100000 $ ) — number of inflorescences. Second line of input contains sequence of $ n-1 $ integer numbers $ p_{2},p_{3},...,p_{n} $ ( $ 1<=p_{i}&lt;i $ ), where $ p_{i} $ is number of inflorescence into which the apple from $ i $ -th inflorescence rolls down.

输出格式

Single line of output should contain one integer number: amount of apples that Arcady will be able to collect from first inflorescence during one harvest.

输入输出样例

输入样例 #1

3
1 1

输出样例 #1

1

输入样例 #2

5
1 2 2 2

输出样例 #2

3

输入样例 #3

18
1 1 1 4 4 3 2 2 2 10 8 9 9 9 10 10 4

输出样例 #3

4

说明

In first example Arcady will be able to collect only one apple, initially situated in $ 1 $ st inflorescence. In next second apples from $ 2 $ nd and $ 3 $ rd inflorescences will roll down and annihilate, and Arcady won't be able to collect them. In the second example Arcady will be able to collect 3 apples. First one is one initially situated in first inflorescence. In a second apple from $ 2 $ nd inflorescence will roll down to $ 1 $ st (Arcady will collect it) and apples from $ 3 $ rd, $ 4 $ th, $ 5 $ th inflorescences will roll down to $ 2 $ nd. Two of them will annihilate and one not annihilated will roll down from $ 2 $ -nd inflorescence to $ 1 $ st one in the next second and Arcady will collect it.

题意翻译

从前有一只名为 NaCly_Fish 的神鱼，她有一棵苹果树。 有一天苹果熟了，每个点都有一个苹果。神鱼用魔法让苹果从树上掉了下来。 每一秒，不在根上的苹果会掉到它的父节点上。在根上的苹果会被神鱼吃掉。 如果某一个点上有不小于 $2$ 个苹果，那么它们会两两抵消。即：$x$ 个苹果会变成 $x \bmod 2$ 个。 神鱼 NaCly_Fish 想知道，她能吃到几个苹果。