4309. 树上查询

【题目描述】

COGS 评测机过慢，将时限开到最大，和做法无关，std 可以跑进 3s。

给定一颗 $n$ 个点的有根树，其中 $1$ 号节点为根，其中每个点 $x$ 有点权 $a_x$。

定义两个点之间的距离 $dist(x, y)$ 表示 $x$ 到 $y$ 的路径经过的边的个数。

定义两个点之间的加权距离 $w(x, y)$ 为 $dist(x, y) \oplus a_y$。

给定 $q$ 此查询，每次给定一个点 $x$ 和一个限制 $k$。

查询 $x$ 子树内所有距离 $x$ 不超过 $k$ 的点 $y$ 的 $w(x, y)$ 之和（包括点 $x$）。

【输入格式】

第一行一个整数 $n$ 表示树的点数。

接下来一行 $n$ 个整数表示点的点权序列 $a$。

接下来一行 $n - 1$ 个整数，第 $i$ 个整数表示第 $i + 1$ 个点的父亲节点编号

接下来一行一个整数 $q$ 表示查询次数。

接下来 $q$ 行，每行两个整数 $x, k$ 表示一次查询。

【输出格式】

共 $q$ 行，每行一个整数表示查询的答案。

【样例输入】

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

【数据规模与约定】

数据按以下方式分组：

第一组 $12pts$：满足 $n,q \le 100$。

第二组 $4pts$：满足 $n, q \le 1e4, k \le 100$。

第三组 $12pts$：满足 $n \le 1e6, q,k \le 500$。

第四组 $24pts$：满足 $n \le 1e6, q,k \le 5000$。

第五组 $32pts$：满足 $n, q \le 1e6$，对于第 $i$ 个点的父亲 $p_i$，满足 $p_i = i - 1$。

第六组 $16pts$：满足 $n,q \le 1e6$。

对于所有数据，如果没有特殊规定，均有 $x, k \le n, a\le 2^{30}$。

大洋里