Paternity Testing

You have a tree of $n$ nodes labeled $1$ through $n$. The tree is rooted at node $1$. A function $cnt(v, l, r)$ is the number of nodes in the subtree of node $v$ whose labels are between $l$ and $r$ inclusive. You must answer $q$ queries. A query is a pair $(l_i, r_i)$. The answer to a query is the sum $\sum_{l \le i \le r} cnt(i, l, r)$.

The first line contains an integer $n$, the number of nodes in the tree.

The next $n - 1$ lines give the parent of each node. The $i$-th of these $n - 1$ lines contains the parent of node $i + 1$.

The following line contains a single integer $q$, the number of queries to answer.

Each of the next $q$ lines contains two numbers $u_i$ and $v_i$, an encoded query.

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

• $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, with $ans_0 = 0$. 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)$