#2037. Slight Hope
Slight Hope
Slight Hope
题目描述
标题: Slight Hope - Problem - QOJ.ac
#4914. Slight Hope
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