P7768 "CGOI-1" Tax Collection

~~An easy check-in problem.~~ Because holding the Ugly Contest cost too much money, ac decided to send Push_Y to collect taxes.

The Ugly Country consists of $n$ cities, and city $1$ is the capital. These $n$ cities are connected by $n-1$ bidirectional roads of length $1$. Starting from city $x$, moving **away from** the capital (that is, moving to child nodes), all cities within distance at most $h$ are the tax-collection range of city $x$. City $i$ needs to pay $a_i$ yuan in income tax. However, since the tax officer Push_Y likes XOR very much, the final tax paid will be the XOR sum of the **tax amounts that should be paid** by every city in its tax-collection range. Push_Y will ask you $m$ queries. In each query, he asks how many **thousand yuan** of income tax city $x$ will collect when the tax-collection distance is $h$. **Simplified statement:** Given a tree with $n$ nodes, rooted at node $1$. The weight of node $i$ is $a_i$. Let $dep_u$ be the depth of node $u$, and the root has depth $1$. There are $q$ queries. Each query gives two integers $x,h$, asking for the value of $\bigoplus_{u\in son(x)\land dep_u-dep_x\le h}a_i$ after dividing by $1000$. Here, $\bigoplus_{i=1}^ni$ means $1\operatorname{xor} 2\operatorname{xor}\cdots\operatorname{xor} n$. Here, $\land$ means “and”, and $\operatorname{xor}$ means XOR.

The first line contains two positive integers $n,m$, representing the number of cities and the number of queries. The second line contains $n$ positive integers $a_i$, representing the income tax amount that each city should pay. The third line contains $n-1$ positive integers. The $i$-th number $f_i$ means that city $i+1$ is connected by a road to city $f_i$. Starting from line $4$, there are $m$ lines. Each line contains two positive integers $x,h$, representing one query.

For each query, output one line with one real number, representing the amount of tax collected by that city. **Keep three digits after the decimal point.**

For $30\%$ of the testdata, $1\le n,m\le 10^3$. For $70\%$ of the testdata, $1\le n,m\le5 \times 10^4$. Among them, $20\%$ of the testdata are chains. For $100\%$ of the testdata, $1\le n,m\le 10^6$, $1 \le a_i \le 10^9$, $1\le x \le n$, $0 \le h \le n$. Translated by ChatGPT 5