Problem Description

Given a rooted tree $T$ with $n$ nodes. The nodes are numbered starting from $1$. The root is node $1$. Each node has a positive integer weight $v_i$.

There are $Q$ queries. For one query, given $(x, k)$, let all nodes in the subtree of node $x$ (including $x$ itself) whose distance to node $x$ is at most $k$ be $c_1, c_2, . . . , c_m$. Then the answer to this query is:

$$(v_{c_1} ⊕ d(c_1, x)) + (v_{c_2} ⊕ d(c_2, x)) + \cdots + (v_{c_m} ⊕ d(c_m, x))$$

Here, $d(x, y)$ denotes the number of edges on the unique simple path between nodes $x$ and $y$ in the tree, and $d(x, x) = 0$. $⊕$ denotes the XOR operation.

Input Format

The first line contains an integer $n$, representing the size of the tree.

The second line contains $n$ integers, representing $v_i$.

The third line contains $n - 1$ integers, in order representing nodes $2$ to $n$. Each integer is the parent index $p_i$ of the corresponding node.

The fourth line contains an integer $Q$.

The next $Q$ lines each contain two integers $x, k$, representing a query $(x, k)$.

Output Format

Output $Q$ lines in total. The $i$-th line contains one integer, representing the answer to the $i$-th query.

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

10
14
4
7
7
55
7
30
7
55

Hint

For $10\%$ of the testdata, $n, Q ≤ 2 \times 10^3$.

For $20\%$ of the testdata, $n, Q ≤ 10^5$.

For another $20\%$ of the testdata, $p_i = i - 1$.

For another $10\%$ of the testdata, $k ≤ 20$.

For another $20\%$ of the testdata, $k = n$.

For another $10\%$ of the testdata, $v_i = 0$.

For $100\%$ of the testdata, $1 ≤ n, Q ≤ 10^6$, $0 ≤ v ≤ 10^9$, $1 ≤ p_i < i$, $1 ≤ x, k ≤ n$.

Translated by ChatGPT 5