P6798 "StOI-2" Simple Tree

Given a rooted tree with root $1$ and $n$ nodes. Each node has a weight $c_{i}$. Define the value $val$ of each node as: the maximum $c_{i}$ among all nodes in the subtree rooted at this node. Define the function $f(x,y)$ as the sum of $val$ over the entire tree after changing $c_{x}$ to $y$. Now you need to answer $q$ queries. Each query gives three values $(l,r,a)$, and you need to compute $\sum\limits_{i=l}^{r}{f(a,i)}$ modulo $998,244,353$.

**This problem is forced online.** The first line contains three positive integers $n$, $q$, and $opt$, representing the number of nodes in the tree, the number of queries, and a value controlling the forced-online behavior. The second line contains $n$ positive integers, representing the weight of each node. The next $n - 1$ lines each contain two positive integers $u_{i}$ and $v_{i}$, representing an edge of the tree. The next $q$ lines each contain three positive integers $l', r', a'$. You need to compute the real $l, r, a$ and then answer the query. - $l = (( l' + opt \times lastans )\bmod n ) + 1$ - $r = (( r' + opt \times lastans )\bmod n ) + 1$ - $a = (( a' + opt \times lastans )\bmod n ) + 1$ Here, $lastans$ is the answer to the previous query, initially $0$. If $l > r$, swap $l$ and $r$.

For each query, output the final answer.

# Sample Explanation The real $(l,r,a)$ are: - $(2,4,1)$ - $(3,5,2)$ - $(2,4,5)$ --- # Constraints For $10\%$ of the testdata: $1 \leq n,q \leq 100$。 For $20\%$ of the testdata: $1 \leq n,q \leq 3000$。 For another $20\%$ of the testdata: $1 \leq l',r',c_{i} \leq 2$。 For another $20\%$ of the testdata: $l' = r'$。 For the first $80\%$ of the testdata: $opt = 0$。 For $100\%$ of the testdata: $1 \leq n,q \leq 5 \times 10^{5}$, $1 \leq c_{i}, a', l', r' \leq n$。 Translated by ChatGPT 5