#2937. [GDKOI]树

[GDKOI]树

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵 nn 个结点的有根树 TT,结点从 11 开始编号,根结点为 11 号结点,每个结点有一个正整数权值 viv_i

QQ 次询问,对于一次询问,给定 (x,k)(x, k),设 xx 号结点的子树内(包含 xx 自身)的所有满足距离 xx 号结 点不超过 kk 的结点编号为 c1,c2,...,ckc_1, c_2, . . . , c_k,则这次询问的答案为:

(vc1d(c1,x))+(vc2d(c2,x))++(vckd(ck,x))(v_{c_1} ⊕ d(c_1, x)) + (v_{c_2} ⊕ d(c_2, x)) + · · · + (v_{c_k} ⊕ d(c_k, x))

其中 d(x,y)d(x, y) 表示树上 xx 号结点与 yy 号结点间唯一简单路径所包含的边数,d(x,x)=0d(x, x) = 0

表示异或运算。

输入格式

第一行一个整数 nn 表示树的大小。

第二行 nn 个整数表示 viv_i

第三行 n1n−1 个整数,依次表示 22 号结点到 nn 号结点,每个结点的父亲编号 pip_i

第四行一个整数 QQ

接下来 QQ 行,每行两个整数 x,kx, k,表示一个 (x,k)(x, k) 的查询。

输出格式

输出共 QQ 行,第 ii 行一个整数表示第 ii 次询问的答案。

输入样例1

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

输出样例1

10
14
4
7
7
55
7
30
7
55

数据范围

对于 10%10\% 的数据,满足 n,Q2×103n, Q ≤ 2×10^3

对于 20%20\% 的数据,满足 n,Q105n, Q ≤ 10^5

对于另外 20%20\% 的数据,满足 pi=i1p_i = i−1

对于另外 10%10\% 的数据,满足 k20k ≤ 20

对于另外 20%20\% 的数据,满足 k=nk = n

对于另外 10%10\% 的数据,满足 vi=0v_i = 0

对于 100%100\% 的数据,满足 1n,Q106,0v109,1pi<i,1x,kn1 ≤ n, Q ≤ 10^6,0 ≤ v ≤ 10^9,1 ≤ p_i < i,1 ≤ x, k ≤ n

GDKOI提高组重现

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-3-15 21:00
结束于
2023-3-25 21:00
持续时间
240 小时
主持人
参赛人数
12