#include<bits/stdc++.h>
#include "september.h"
#include <vector>
using namespace std;
int timee=0;
int start[100005];
int stop[100005];
vector<int>g[100005];
int depth[100005];
int tp[100005];
void dfs(int u)
{
timee++;
start[u]=timee;
tp[timee]=u;
for(auto v:g[u])
{
depth[v]=depth[u]+1;
dfs(v);
}
stop[u]=timee;
}
int dem=0;
int cnt[100005];
pair<int,int>min(pair<int,int>a,pair<int,int>b)
{
if(a.first<=b.first)return a;
return b;
}
pair<int,int> tree[400005];
int lazy[400005];
void init(int id,int l,int r)
{
if(l==r)
{
tree[id].first=1e9+depth[tp[l]];
tree[id].second=l;
return;
}
int mid=(l+r)/2;
init(id*2,l,mid);
init(id*2+1,mid+1,r);
tree[id]=min(tree[id*2],tree[id*2+1]);
}
void push(int id)
{
if(lazy[id]==0)return;
tree[id*2].first+=lazy[id];
tree[id*2+1].first+=lazy[id];
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
void update(int id,int l,int r,int u,int v,int val)
{
if(l>v||r<u)return;
if(l>=u&&r<=v)
{
tree[id].first+=val;
lazy[id]+=val;
return;
}
push(id);
int mid=(l+r)/2;
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
tree[id]=min(tree[id*2],tree[id*2+1]);
}
int lim;
void add(int u)
{
cnt[u]++;
if(cnt[u]==lim)dem++;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
for(int i=0; i<N; i++)cnt[i]=0;
timee=0;
dem=0;
lim=M;
for(int i=1; i<=4*N; i++)lazy[i]=0;
for(int i=0; i<N; i++)g[i].clear();
for(int i=1; i<N; i++)g[F[i]].push_back(i);
dfs(0);
init(1,1,N);
for(int i=0; i<M; i++)
{
S[i].push_back(0);
reverse(S[i].begin(),S[i].end());
}
int cnt_check=0;
int ans=0;
for(int i=1; i<N; i++)
{
for(int j=0; j<M; j++)add(S[j][i]);
int u=S[0][i];
update(1,1,N,start[u],start[u],-1e9);
update(1,1,N,start[u],stop[u],-1);
while(tree[1].first==0)
{
cnt_check++;
update(1,1,N,tree[1].second,tree[1].second,1e9);
}
if(cnt_check==i&&dem==i)ans++;
//cout<<u<<'\n';
}
return ans;
}
