P2720 Xiao A's Gift

**Testdata updated (2018-3-2).**

Xiao A went to school to attend an event, and the school gives out gifts. The school has many gift points. Each gift point has outgoing roads to other gift points and a gift type. To prevent picking up gifts multiple times, these roads are directed and acyclic. Moreover, for any edge from $a$ to $b$, if after removing this edge there exists a node $c$ that can reach both $a$ and $b$, then such an edge does not appear in the graph. In addition, every node except node $1$ has exactly one incoming edge. Xiao A wants to know, for all nodes reachable from a node $S$ (including $S$ itself), how many distinct gift types are there.

- The first line contains the number of gift points $n$ ($n \le 100000$). - The next line contains $n - 1$ integers, representing the parent (in-neighbor) of nodes $2, \dots, n$ respectively; that is, the $i$-th integer is the parent of node $i + 1$. - The next line contains $n$ integers, where the $i$-th integer is the gift ID of node $i$. - The next line contains $m$, the number of queries. - Each of the next $m$ lines contains one node ID, representing a query node.

For each query, output the number of distinct gifts.

Sample Explanation: - Node $1$ can reach nodes $(1, 2, 3, 4)$, with three gift types $(1, 2, 3)$. - Node $2$ can reach nodes $2, 3, 4$, with two gift types $2, 3$. Constraints: | Test point ID | $n$ | $m$ | $c_i$ (color) | |:-:|:-:|:-:|:-:| | $1$ | $\le 10^2$ | $\le 10^2$ | $\le 10^2$ | | $2 \sim 3$ | $\le 10^3$ | $\le 10^3$ | $\le 10^3$ | | $4 \sim 5$ | $\le 10^4$ | $\le 10^4$ | $\le 20$ | | $6$ | $\le 5 \times 10^4$ | $\le 5 \times 10^4$ | $\le 5 \times 10^4$ | | $7 \sim 8$ | $\le 10^5$ | $\le 5 \times 10^4$ | $\le 6 \times 10^4$ | Translated by ChatGPT 5