「RdOI R3」RBT

你有一棵以 $1$ 为根，编号为 $1\sim n$ 的有根树，第 $i$ 号节点上有一个整数权值 $a_i$。同时每一个点都被染上了红色或蓝色。初始所有点全是红色点。你需要维护这棵树，进行 $q$ 次操作。操作分若干种，具体格式如下： - `1 x v` ：使 $x$ 节点的子树中的每个节点的权值增加 $v$ 并对 $p$ 取模。 - `2 x v`：将 $a_x$ 赋值为 $v$。**注意不是赋值整棵子树。** - `3 x`：将 $x$ 号点染成蓝色，设 $j$ 节点为 $x$ 号节点在它的**红色**兄弟节点中**编号**（不是权值）排名的前驱，将 $x$ 节点连接父亲的边删除。然后将 $x$ 节点作为儿子节点接到 $j$ 节点上，如果 $x$ 节点没有红色兄弟节点或 $x$ 节点的红色兄弟节点的编号均比 $x$ 大则什么都不做。 - `4 x`：设 $S$ 为 $x$ 的子树中的节点的权值中出现次数为奇数的数组成的集合。输出集合中的每个数的 $k$ 次方之和，对 $998244353$ 取模。即 $(\sum_{z\in S}z^k)\bmod 998244353$。 特别的，数据保证每个点只能被执行 $3$ 操作至多 $1$ 次。也就是说不会出现对一个蓝色点进行 $3$ 操作的情况。

第一行四个整数 $n,q,p,k$。 第二行 $n$ 个整数，代表初始的 $a_1,a_2,\cdots,a_n$。 接下来 $n-1$ 行，每行两个整数 $f,t$。表示一条连接 $f \leftrightarrow t$ 的双向树边。 接下来 $q$ 行，每行两个或三个整数 $op,x(,v)$。

对于每个询问操作，输出一行一个整数表示答案。

10 10 500 1
3 2 1 2 1 3 2 1 3 4
1 4
7 8
3 6
8 10
2 3
2 5
8 9
7 2
2 1
4 1
1 3 1
2 1 2
4 1
4 3
4 6
1 4 1
3 7
1 5 1
4 5

10
5
6
4
12

### 样例解释 #### 样例 \#1 - 询问 `4 1`，子树中点的权值分别为 $3,2,1,2,1,3,2,1,3,4$，$S$ 集合为 $\{1,2,3,4\}$，故答案为 $10$。 - 修改 `1 3 1`，树中各点权值变为 $3,2,2,2,1,4,2,1,3,4$。 - 修改 `2 1 2`，树中各点权值变为 $2,2,2,2,1,4,2,1,3,4$。 - 询问 `4 1`，子树中点的权值分别为 $2,2,2,2,1,4,2,1,3,4$，$S$ 集合为 $\{2,3\}$，故答案为 $5$。 - 询问 `4 3`，子树中点的编号为 $3,6$，权值分别为 $2,4$，$S$ 集合为 $\{2,4\}$，故答案为 $6$。 - 询问 `4 6`，由于这是一个叶子节点，子树中点的权值为它本身的权值 $4$，$S$ 集合为 $\{4\}$，故答案为 $4$。 - 修改 `1 4 1`，树中各点权值变为 $2,2,2,3,1,4,2,1,3,4$。 - 修改 `3 7`，将 $7$ 涂成蓝色，删除树中的边 $2\leftrightarrow 7$，并将 $7$ 作为儿子节点接到 $5$ 上。 - 修改 `1 5 1`，树中各点权值变为 $2,2,2,3,2,4,3,2,4,5$。 - 询问 `4 5`，子树中各点编号为 $5,7,8,9,10$，权值分别为 $2,3,2,4,5$，$S$ 集合为 $\{3,4,5\}$，故答案为 $12$。 --- ### 数据范围 **本题采用捆绑测试。** 对于所有数据，$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 | 分值 | 特殊限制 | | ------- | ---- | ------------------------------------------- | | $1$ | $10$ | $op,a_i,x,v$ 和初始树的形态均等概率随机生成 | | $2$ | $90$ | 无 |