P6798 「StOI-2」简单的树

给定一棵以 $1$ 为根，由 $n$ 个点组成的有根树，每个点有点权 $c_{i}$ 。 定义每个点的 $val$ 值为：以它为根的子树内所有 $c_{i}$ 的最大值。 定义函数 $f(x,y)$ 表示将 $c_{x}$ 改为 $y$ 后整棵树的 $val$ 值之和。 现在请您回答 $q$ 组询问，每次询问给定 $3$ 个量 $(l,r,a)$ ，请求出 $\sum\limits_{i=l}^{r}{f(a,i)}$ 对 $998,244,353$ 取模的结果。

**本题强制在线** 第一行三个正整数，$n$、$q$ 和 $opt$，分别表示树的点数、询问数和控制强制在线的量。 第二行 $n$ 个正整数，表示每个点的点权。 接下来 $n-1$ 行，每行两个正整数 $u_{i}$ 和 $v_{i}$，表示树的每一条边。 接下来 $q$ 行，每行三个正整数 $l',r',a'$ ，请计算出真实的 $l,r,a$ 后完成询问。 - $l = (( l' + opt \times lastans )\bmod n )$ $+ 1$ - $r = (( r' + opt \times lastans )\bmod n )$ $+ 1$ - $a = (( a' + opt \times lastans )\bmod n )$ $+ 1$ 其中 $lastans$ 表示上一组询问的答案，初始为 $0$ 。 如果此时出现 $l > r$ 的情况，请交换 $l$ 和 $r$ 。

对于每组询问，输出最终的答案。

## 样例解释 真实的 $(l,r,a)$ 为： - $(2,4,1)$ - $(3,5,2)$ - $(2,4,5)$ --- ## 数据范围 对于 $10\%$ 的数据：$1 \leq n,q \leq 100 $ 。 对于 $20\%$ 的数据：$1 \leq n,q \leq 3000 $ 。 对于另 $20\%$ 的数据：$1 \leq l',r',c_{i} \leq 2 $ 。 对于另 $20\%$ 的数据：$l'=r'$ 。 对于前 $80\%$ 的数据：$opt=0$ 。 对于 $100\%$ 的数据：$1 \leq n,q \leq 5 \times 10^{5} ，1 \leq c_{i} , a' , l' , r' \leq n$ 。