P7826 "RdOI R3" RBT

You have a rooted tree with root $1$, with nodes numbered $1\sim n$. Node $i$ has an integer weight $a_i$. At the same time, every node is colored red or blue. Initially, all nodes are red. You need to maintain this tree and process $q$ operations. There are several types of operations, with the following formats: - `1 x v`: Increase the weight of every node in the subtree of node $x$ by $v$, and take modulo $p$. - `2 x v`: Set $a_x$ to $v$. **Note that this does not assign the entire subtree.** - `3 x`: Color node $x$ blue. Let node $j$ be the predecessor of node $x$ in the ranking by **node index** (not by weight) among its **red** sibling nodes. Delete the edge connecting node $x$ to its parent. Then attach node $x$ as a child of node $j$. If node $x$ has no red siblings, or all its red siblings have indices greater than $x$, then do nothing. - `4 x`: Let $S$ be the set of weights in the subtree of $x$ whose occurrence counts are odd. Output the sum of the $k$-th power of each number in the set, modulo $998244353$. That is, $(\sum_{z\in S}z^k)\bmod 998244353$. In particular, the testdata guarantees that each node can be operated by operation `3` at most once. In other words, there will be no case where operation `3` is applied to a blue node.

The first line contains four integers $n,q,p,k$. The second line contains $n$ integers, representing the initial $a_1,a_2,\cdots,a_n$. The next $n-1$ lines each contain two integers $f,t$, representing an undirected tree edge $f \leftrightarrow t$. The next $q$ lines each contain two or three integers $op,x(,v)$.

For each query operation, output one integer per line as the answer.

### Sample Explanation #### Sample \#1 - Query `4 1`: The weights in the subtree are $3,2,1,2,1,3,2,1,3,4$. The set $S$ is $\{1,2,3,4\}$, so the answer is $10$. - Update `1 3 1`: The weights of all nodes become $3,2,2,2,1,4,2,1,3,4$. - Update `2 1 2`: The weights of all nodes become $2,2,2,2,1,4,2,1,3,4$. - Query `4 1`: The weights in the subtree are $2,2,2,2,1,4,2,1,3,4$. The set $S$ is $\{2,3\}$, so the answer is $5$. - Query `4 3`: The nodes in the subtree are $3,6$, with weights $2,4$. The set $S$ is $\{2,4\}$, so the answer is $6$. - Query `4 6`: Since this is a leaf node, the subtree contains only itself with weight $4$. The set $S$ is $\{4\}$, so the answer is $4$. - Update `1 4 1`: The weights of all nodes become $2,2,2,3,1,4,2,1,3,4$. - Update `3 7`: Color $7$ blue, delete the edge $2\leftrightarrow 7$, and attach $7$ as a child of $5$. - Update `1 5 1`: The weights of all nodes become $2,2,2,3,2,4,3,2,4,5$. - Query `4 5`: The nodes in the subtree are $5,7,8,9,10$, with weights $2,3,2,4,5$. The set $S$ is $\{3,4,5\}$, so the answer is $12$. --- ### Constraints **This problem uses bundled testdata.** For all testdata, $1\le x\le n\le 10^5$, $1\le q \le 10^5$, $0 \le a_i, v < p \le 500$, $p\ne 0$, $0\le k \le 10^9$. | subtask | score | special constraints | | ------- | ----- | ----------------------------------------------------------------------- | | $1$ | $10$ | $op,a_i,x,v$ and the initial tree shape are generated uniformly at random | | $2$ | $90$ | none | Translated by ChatGPT 5