题目背景
Slight Light, Slight Hope.
题目描述
小 W 有一棵 n 个点的有根树(节点标号为 1∼n),以 1 号点为根。其中 i 号点的点权为 ai。
假设 i 号点的父节点为 fi(方便起见认为 f1=0),小 W 发现这棵树有一个奇妙的性质:对于任意整数 i∈[2,n],满足 fi−1≤fi<i。
小 C 对此很感兴趣,因此她决定进行 q 次询问,第 i 次询问给出一个区间 [li,ri],求:
(ri∑x=liri∑y=li[li≤LCA(x,y)≤ri]⋅ax⋅ay)mod
其中 \operatorname{LCA}(x,y) 表示 x 和 y 的最近公共祖先。
因为小 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 lst,r_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^5,0\le a_i < 998244353,1\le l_i\le r_i\le n。保证对于任意整数 i\in[2,n],满足 f_{i-1}\le f_i < i。