P7768 「CGOI-1」收税

~~签到题~~ 由于举办选丑大赛消耗了太多钱财，ac 决定派出 Push_Y 去收税。

丑国由 $n$ 座城市组成，编号 $1$ 的为首都。这 $n$ 座城市由 $n-1$ 条长度为 $1$ 的双向道路连接。从编号为 $x$ 的城市出发，往**远离**首都的方向（即往儿子节点走），距离不超过 $h$ 的就是这座城市要收税的范围。 第 $i$ 座城市将要上缴 $a_i$ **元**的所得税。但由于收税官 Push_Y 很喜欢异或，因此每座城市最终上缴的所得税将是在其收税范围内每座城市**应缴税额**的异或和。 Push_Y 将向你提出 $m$ 个询问，他将问你城市 $x$ 在收税距离为 $h$ 时将收到多少**千元**的所得税。 **简化版题意：** 给定一棵 $n$ 个点的树，根节点为 $1$ 号点，第 $i$ 个点的点权为 $a_i$，$dep_u$ 表示 $u$ 点的深度，根节点的深度为 $1$，$q$ 次询问，每次给定两个整数 $x,h$，表示询问 $\bigoplus_{u\in son(x)\land dep_u-dep_x\le h}a_i$ 除以 $1000$ 后的值。 其中 $\bigoplus_{i=1}^ni$ 表示 $1\operatorname{xor} 2\operatorname{xor}\cdots\operatorname{xor} n$。 此处 $\land$ 是“且”，$\operatorname{xor}$ 是异或。

第一行两个正整数 $n,m$，表示城市数和询问数。 第二行 $n$ 个正整数 $a_i$， 表示每座城市应缴的所得税额。 第三行 $n-1$ 个正整数，其中第 $i$ 个数 $f_i$ 表示城市 $i+1$ 与城市 $f_i$ 有一条路相连。 从第 $4$ 行开始 $m$ 行，每行两个正整数 $x,h$，表示一组询问。

对于每组询问，输出一行，一个实数，表示这座城市收取的税额。 **答案保留三位小数。**

对于 $30\%$ 的数据，$1\le n,m\le 10^3$。 对于 $70\%$ 的数据，$1\le n,m\le5 \times 10^4$。其中有 $20\%$ 的数据是链。 对于 $100\%$ 的数据，$1\le n,m\le 10^6$，$1 \le a_i \le 10^9$，$1\le x \le n$，$0 \le h \le n$。