QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+9]

# 4914. Slight Hope

Statistics

题目背景

Slight Light, Slight Hope.

题目描述

小 W 有一棵 n 个点的有根树(节点标号为 1n),以 1 号点为根。其中 i 号点的点权为 ai

假设 i 号点的父节点为 fi(方便起见认为 f1=0),小 W 发现这棵树有一个奇妙的性质:对于任意整数 i[2,n],满足 fi1fi<i

小 C 对此很感兴趣,因此她决定进行 q 次询问,第 i 次询问给出一个区间 [li,ri],求:

(rix=liriy=li[liLCA(x,y)ri]axay)mod

其中 \operatorname{LCA}(x,y) 表示 xy 的最近公共祖先。

因为小 C 在每次询问时都迫切地想要知道答案,所以本题强制在线(具体方式见输入格式)。

输入格式

第一行包含两个正整数 n,q,分别表示节点个数和询问次数。

第二行 n 个非负整数 a_{1\sim n},表示每个点的点权。

第三行 n-1 个正整数 f_{2\sim n},表示每个点的父节点。

接下来 q 行,每行两个非负整数 l_i',r_i'。假设上一次询问的答案为 lst(对于第一个询问,认为 lst=0),则真正的 l_i=l_i'\oplus lstr_i=r_i'\oplus lst,其中 \oplus 表示按位异或运算。

输出格式

q 行,每行一个整数表示对应询问的答案。(向 998244353 取模)

样例

input

6 3
1 2 3 4 5 6
1 1 2 2 3
1 2
11 12
131 132

output

9
130
441

explanation

第一个询问的区间为 [1,2]\operatorname{LCA}(1,1)=1,\operatorname{LCA}(1,2)=1,\operatorname{LCA}(2,1)=1,\operatorname{LCA}(2,2)=2 都符合条件。答案为 1\times 1+1\times2+2\times1+2\times2=9

第二个询问的区间为 [2,5]\operatorname{LCA}(2,2)=2,\operatorname{LCA}(2,4)=2,\operatorname{LCA}(2,5)=2,\operatorname{LCA}(3,3)=3,\operatorname{LCA}(4,2)=2,\operatorname{LCA}(4,4)=4,\operatorname{LCA}(4,5)=2,\operatorname{LCA}(5,2)=2,\operatorname{LCA}(5,4)=2,\operatorname{LCA}(5,5)=5 符合条件,其余点对 \operatorname{LCA}1。答案为 130

第三个询问的区间为 [1,6],由于 \operatorname{LCA} 肯定在 [1,n] 范围内,任意点对都满足条件。答案为 441

限制与约定

  • Subtask 1 (20\%) :n,q \leq 5\times10^3
  • Subtask 2 (20\%) :n,q \leq 5\times10^4
  • Subtask 3 (20\%) :树的形态随机
  • Subtask 4 (40\%) :无特殊限制

对于 100\% 的数据,1\le n,q\le2.5\times10^50\le a_i < 9982443531\le l_i\le r_i\le n。保证对于任意整数 i\in[2,n],满足 f_{i-1}\le f_i < i