根付き木が与えられるため、頂点 \(K\) の部分木の大きさを求める問題です。

部分木のサイズは「 \(1\) + 自分の子の部分木のサイズの総和」であることに注意すれば、以下のようなアルゴリズムですべての頂点 \(i\) について \(O(N)\) で求められます。

1. 長さ \(N\) ですべての要素が \(1\) の配列 \(S\) を用意する

2. 自分のすべての子について「処理が終わった」頂点 \(v\) を探す

   • \(v\) が根ならばアルゴリズムを終了する
   • そうでないなら \(v\) の親を \(p\) とし、\(S[p] += S[v]\) とし、\(v\) の「処理が終わった」とする。そして、2 に戻る

一般的な木であれば「既に処理が終わった子の個数」を管理しながら que などを用いてシミュレートすればよいです。

今回の問題では、制約の条件から頂点 \(v\) を降順に見るだけで、常に「すべての子が処理が終わった」状態になります。

計算量は \(O(N)\) です。

実装例

n, k = map(int, input().split())
p = [int(x)-1 for x in input().split()] if n != 1 else []
p = [-1] + p

s = [1] * n
for i in reversed(range(1, n)):
    s[p[i]] += s[i]
print(n - s[k-1])