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.
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.
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.
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.
| Subtask | Score |
|---|---|
| 1 | 27 |
| 2 | 20 |
| 3 | 22 |
| 4 | 31 |
| 5 | 0 |