P10107 [GDKOI2023 Senior] Tree

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.

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 $Q$ lines in total. The $i$-th line contains one integer, representing the answer to the $i$-th query.

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