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$ 取模的结果。

无

无

## 样例解释 真实的 $(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$ 。