// https://codeforces.com/problemset/problem/208/E

#include "stdafx.h"

//#include <bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pb push_back

using namespace std;

const int N=100010;?

int n,m;

int acc[N][25],siz[N],dep[N],son[N];

int cnt[N],len = 16; //森林深度最大值, CF測(cè)試15錯(cuò)誤

int anw[N];

std::vector<int > tr;

std::vector<pii > v[N];

std::vector<int > e[N];

void dfs1(int now,int p)

{

dep[now] = dep[p]+1; cout<<"now="<<now<<", dep[now]="<<dep[now] <<endl;

acc[now][0] = p;// father

siz[now] = 1; // 子樹大小

for(int i=1;(1<<i)<=dep[now];i++){

acc[now][i] = acc[acc[now][i-1]][i-1]; //2^i級(jí)祖先就是2^(i-1)級(jí)祖先的2^(i-1)祖先

cout<<", i="<<i<<",? 1<<i="<<(1<<i)<<", 1="<<1<<endl;

}

for(auto spot:e[now])

{

if(spot==p) continue;

dfs1(spot,now);

siz[now] += siz[spot];// 子樹大小

if(siz[son[now]]<siz[spot]) son[now] = spot;// 重兒子

}

}

void add(int now,int p,int value,int wson)

{

cnt[dep[now]] += value;// 假設(shè)now的dep[now]-1代祖先為x，則x的dep[now]-1代子孫個(gè)數(shù)加1

for(auto spot:e[now])

{

if(spot==p||spot==wson) continue;

add(spot,now,value,wson);

}

}

void dfs(int now,int p,int keep)

{

for(auto spot:e[now])

{

if(spot==p||spot==son[now]) continue;

dfs(spot,now,0);

}

if(son[now]) dfs(son[now],now,1);

add(now,p,1,son[now]);

for(auto t:v[now])

{

int x = t.first,id = t.second;

anw[id] = cnt[dep[now]+x]-1; //now 的x代子孫個(gè)數(shù)cnt[dep[now]+x]，減去他本身這個(gè)點(diǎn)，即為表親個(gè)數(shù)

cout<<"id="<<id<<", dep[now]+x= "<<dep[now]+x<<endl;

}

if(!keep) add(now,p,-1,0);

}

signed main()

{

//cin>>n;

n=9;

int X[16] ={0, 1, 1 ,0 ,4 ,4,5,6,6};

for(int i=1;i<=n;i++)

{

int x;

//cin>>x;

x=X[i-1];

if(x) e[i].pb(x),e[x].pb(i);

else tr.pb(i);

}

for(auto t:tr) dfs1(t,0);

//cin>>m;

m=8;

int QU[8][2]={

1, 1,

1 ,2,

2, 1,

2 ,2,

4 ,1,

5, 1,

6 ,1,

7,2};

for(int i=1;i<=m;i++)

{

int a,b;

//cin>>a>>b;

a=QU[i-1][0];

b=QU[i-1][1];

for(int j=len;j>=0;j--)

{? ?// 如果b=7=2^2+2^1+2^0, 則3次可以倍增到7代祖先

if(b>>j&1) a = acc[a][j]; //倍增到b代祖先， acc[a][j]代表a的2的j次方祖先。

}

v[a].pb(make_pair(b,i));

}

for(auto t:tr) dfs(t,0,0);

for(int i=1;i<=m;i++) cout<<anw[i]<<" \n"[i==m];

return 0;

}