Description

一天小g遇到了一棵神奇的苹果树，树上有n个苹果并将这n个苹果按1-n标号，每个苹果都会向下落，单位时间将完成一次掉落。现在规定只有当苹果掉到1时才能采摘，除了1位置,其他位置的苹果每一次将落到对应的pi上，直至掉落至1位置。现在规定同一时间，同一位置有偶数个苹果时，它们消失不见，如果是奇数则剩下一个。保证最后所有的苹果都会落到1位置上，问最后小g将收获多少个苹果。

 

Input

第一行一个整数n(2 <= n <= 100000)，表示苹果的个数；

第二行为n-1个整数pi (1 <= pi < i)。

Output

 输出一个整数，表示S的最大值。

 

Sample Input

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

Sample Output

1 3 4

HINT

 

小g刚开始拿到1位置上的苹果，然后2位置上的苹果落到1上，3、4、5位置的苹果落在2位置上。最后小g将得到这个两个苹果，总共3个苹果。

题解：

通过分析我们其实可以发现只要考虑到1位置的步数就可以了。

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,res=0,tmp;
int p[N],t[N],s[N],c[N];
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(~scanf("%d",&n)){
        res = 0;

        memset(p,0,sizeof(p));
        memset(t,0,sizeof(t));
        memset(s,0,sizeof(s));
        memset(c,0,sizeof(c));
        for(int i=2;i<=n;i++)scanf("%d",&p[i]);
        for(int i=1;i<=n;i++)tmp=c[p[i]]+1,s[tmp]++,c[i]=tmp;
        for(int i=1;i<=n;i++)if(s[i]&1)res++;
        cout<<res<<endl;
    }
}