#include "september.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, m;
struct Fenwick
{
int tree[MAXN];
void reset()
{
std::fill(tree, tree + n + 1, 0);
}
void update(int idx, int val)
{
for (; idx <= n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int idx)
{
int res = 0;
for (; idx ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
void rangeUpdate(int l, int r)
{
update(l, 1);
update(r + 1, -1);
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
};
bool added[MAXN];
Fenwick childTree;
Fenwick parentTree;
std::vector <int> g[MAXN];
int count[MAXN];
int count2[MAXN];
int in[MAXN];
int out[MAXN];
int timer;
void dfs(int node)
{
in[node] = ++timer;
for (const int &u : g[node])
{
dfs(u);
}
out[node] = timer;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
n = N;
m = M;
for (int i = 1 ; i <= n ; ++i)
{
g[i].clear();
added[i] = 0;
count[i] = count2[i] = 0;
}
for (int i = 1 ; i < n ; ++i)
{
g[F[i] + 1].push_back(i + 1);
}
childTree.reset();
parentTree.reset();
timer = 0;
dfs(1);
for (int i = 1 ; i <= n ; ++i)
{
childTree.update(i, 1);
}
int badCnt = 0;
int answer = 0;
for (int i = 0 ; i < n - 1 ; ++i)
{
for (int person = 0 ; person < m ; ++person)
{
S[person][i]++;
int node = S[person][i];
count2[count[node]]--;
count[node]++;
count2[count[node]]++;
if (!added[node])
{
badCnt += childTree.query(in[node], out[node]);
childTree.update(in[node], -1);
parentTree.rangeUpdate(in[node], out[node]);
badCnt -= parentTree.query(in[node]);
added[node] = true;
}
}
if (badCnt == 0 && count2[m] == i + 1)
{
answer++;
}
}
return answer;
}
