#2037. Slight Hope

    ID: 2037 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest761来源:qoj.ac数据:公开样例树上算法线段树

Slight Hope

Slight Hope

题目描述

标题: Slight Hope - Problem - QOJ.ac

#4914. Slight Hope

Statistics

The problem was used in the following contests:

题目背景

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],求:

(∑x=liri∑y=liri[li≤LCA⁡(x,y)≤ri]⋅ax⋅ay)mod998244353

其中 LCA⁡(x,y) 表示 x 和 y 的最近公共祖先。

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

输入格式

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

第二行 n 个非负整数 a1∼n,表示每个点的点权。

第三行 n−1 个正整数 f2∼n,表示每个点的父节点。

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

输出格式

共 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],LCA⁡(1,1)=1,LCA⁡(1,2)=1,LCA⁡(2,1)=1,LCA⁡(2,2)=2 都符合条件。答案为 1×1+1×2+2×1+2×2=9。

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

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

限制与约定

  • Subtask 1 (20%) :n,q≤5×103
  • Subtask 2 (20%) :n,q≤5×104
  • Subtask 3 (20%) :树的形态随机
  • Subtask 4 (40%) :无特殊限制

对于 100% 的数据,1≤n,q≤2.5×105,0≤ai<998244353,1≤li≤ri≤n。保证对于任意整数 i∈[2,n],满足 fi−1≤fi<i。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6 3
1 2 3 4 5 6
1 1 2 2 3
1 2
11 12
131 132
9
130
441