Problem C
Boxes
There are $N$ boxes, indexed by a number from $1$ to $N$. Each box may (or not may not) be put into other boxes. These boxes together form a tree structure (or a forest structure, to be precise).
You have to answer a series of queries of the following form: given a list of indices of the boxes, find the total number of boxes that the list of boxes actually contain.
Consider, for example, the following five boxes.
-
If the query is the list “1”, then the correct answer is “5”, because box 1 contains all boxes.
-
If the query is the list “4 5”, then the correct answer is “2”, for boxes 4 and 5 contain themselves and nothing else.
-
If the query is the list “3 4”, then the correct answer is “2”.
-
If the query is the list “2 3 4”, then the correct answer is “4”, since box 2 also contains box 5.
-
If the query is the list “2”, then the correct answer is “3”, because box 2 contains itself and two other boxes.
Input
The first line contains the integer $N$ ($1 \leq N \leq 200\, 000$), the number of boxes.
The second line contains $N$integers. The $i$th integer is either the index of the box which contains the $i$th box, or zero if the $i$th box is not contained in any other box.
The third line contains an integer $Q$ ($1 \leq Q \leq 100\, 000$), the number of queries. The following $Q$ lines will have the following format: on each line, the first integer $M$ ($1 \leq M \leq 20$) is the length of the list of boxes in this query, then $M$ integers follow, representing the indices of the boxes.
Output
For each query, output a line which contains an integer representing the total number of boxes.
Sample Input 1 | Sample Output 1 |
---|---|
5 0 1 1 2 2 5 1 1 2 4 5 2 3 4 3 2 3 4 1 2 |
5 2 2 4 3 |