QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

# 4914. Slight Hope

Statistics

题目背景

$\texttt{Slight Light, Slight Hope.}$

题目描述

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

假设 $i$ 号点的父节点为 $f_i$(方便起见认为 $f_1=0$),小 W 发现这棵树有一个奇妙的性质:对于任意整数 $i\in[2,n]$,满足 $f_{i-1}\le f_i < i$。

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

$$ \left(\sum_{x=l_i}^{r_i}\sum_{y=l_i}^{r_i}[l_i\le \operatorname{LCA}(x,y)\le r_i]\cdot a_x\cdot a_y\right)\bmod998244353 $$

其中 $\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$。