406568: GYM102441 J Paternity Testing

You have a tree consisting of $$$n$$$ nodes labeled from $$$1$$$ to $$$n$$$. The tree is rooted at node $$$1$$$. A function $$$cnt(v, l, r)$$$ is defined as the number of nodes in a subtree of node $$$v$$$, that have indices from $$$l$$$ to $$$r$$$ inclusive. You are required to answer $$$q$$$ queries. The query is represented by a pair $$$(l_i, r_i)$$$. The answer to the query is a sum $$$\sum_{l \le i \le r} cnt(i, l, r)$$$.

First line contains an integer $$$n$$$ — the number of nodes in the tree.

Next $$$n - 1$$$ lines indicate ancestors of the nodes in the tree. Each $$$i$$$-th line of those $$$n - 1$$$ lines contains the ancestor's index for the $$$i + 1$$$-th node in the tree.

The following line contains a single integer $$$q$$$ — the number of queries to be answered.

Each of the next $$$q$$$ lines contains two numbers $$$u_i$$$ and $$$v_i$$$ — encoded queries.

$$$$$$ 1 \le n \le 50000 $$$$$$ $$$$$$ 1 \le q \le 50000 $$$$$$ $$$$$$ 0 \le u_i, v_i \le 10^9 $$$$$$

Let $$$ans_i$$$ be the answer to the $$$i$$$-th query ($$$ans_0 = 0$$$). Then, the parameters of the $$$i$$$-th query are: $$$$$$ x_i = 1 + ((u_i \oplus ans_{i-1}) \mod n) $$$$$$ $$$$$$ y_i = 1 + ((v_i \oplus ans_{i-1}) \mod n) $$$$$$ $$$$$$ l_i = min(x_i, y_i) $$$$$$ $$$$$$ r_i = max(x_i, y_i) $$$$$$

Print $$$q$$$ lines. The $$$i$$$-th line should contain the answer to the query $$$(l_i, r_i)$$$.

9
1
2
3
4
5
5
7
8
5
0 8
1 2
2 3
4 5
6 7

42
8
3
3
3