cousin

Problem Description

Gug the Amoeba has a long family heritage. There are a total of N amoeba in his family, with the eldest of them all being Amoeba 0. For all other amoebas, they have a single parent. Namely, amoeba i has parent Pi. It is guaranteed that there will be no loops in the family tree, meaning that no direct or indirect parent of an amoeba will be itself.

We call a pair of distinct amoebas k-cousins if they share a common k-th parent. Gug wants to know, for some amoebas in his family, how many k-cousins they have.

Implementation Details

This is a function call problem. You are to implement 2 functions:

void init(int N, int P[])

This function will be called before any of the other functions in your code. N is the number of amoebas in Gug's family tree and P is the parent array of his family tree. Since Amoeba 0 has no parent, P0 = -1.

int count_cousins(int X, int K)

This function should return the number of K-cousins that Amoeba X has. It is guaranteed that Amoeba X has at least K parents.

Limits

Subtask 1 (27%): 1 ≤ N ≤ 1000, Number of calls to count_cousins ≤ 3000.

Subtask 2 (20%): 1 ≤ N ≤ 200000, K ≤ 5, Number of calls to count_cousins ≤ 300000.

Subtask 3 (22%): 1 ≤ N ≤ 200000, K is a constant throughout all calls to count_cousins, Number of calls to count_cousins ≤ 300000.

Subtask 4 (31%): 1 ≤ N ≤ 200000, Number of calls to count_cousins ≤ 300000.

Subtask 5 (0%): Sample Testcases.

Sample Interaction

init(7, [-1, 0, 1, 1, 0, 4, 4]) will be called.
count_cousins(2, 1) is called. It should return 1.
count_cousins(6, 1) is called. It should return 1.
count_cousins(3, 2) is called. It should return 3.

Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 256MB
No. of ACs: 6
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 27
2 20
3 22
4 31
5 0