P9398 「DBOI」Round 1 烟花

回忆本身就是惩罚，惩罚那些不愿往前走的人，将他们困在那条小巷子里，怎么也走不出去。 每一年都有烟花，唯独那一年的烟花最好看。 “我要对烟花许愿，许我们永远在一起。” “就算不许愿，我们也会永远在一起的。” 再后来，死了的人被葬在了那座山上，活着的人被记忆困在了那条巷中。今天的我们听到这个故事，只是想再放一次故事里的烟花，放给那些再没能陪身旁的人看到一次烟花的人。

烟花在夜空中绽放连成一片，我们把这些连成一片的烟花看成一棵含有 $n$ 个点的有根树，根为最早点燃的烟花 $1$。 烟花有红蓝两种颜色，为了方便，我们对这棵树黑白染色。最初有 $p$ 个限制，一条限制形如 $(x_i,y_i)$，表示树中编号为 $x_i$ 的点的子树中黑点只能**恰好**有 $y_i$ 个。当年，他们认为满足其**子树内所有有限制点的限制**的子树是**均好的子树**。显然，要想使一个子树成为均好的子树，可能有**多种染色方法**。 你需要回答以下两种询问： - `Z k c`，表示给点 $k$ 以均等概率在 $[0,c]$ 中选择一个数 $f$，然后给点 $k$ 直接加上 $f$ 个没有限制的儿子，其它儿子状态不变。问点 $k$ 为根的子树成为**均好的子树**的期望染色方法数量。 - `H k`，表示如果去掉 $k$ 的所有有限制儿子的限制，询问 $k$ 为根的子树成为**均好的子树**的染色方法数量。 我们并没有必要点燃更多的烟花，因此所有的询问都是相互独立的，没有询问会真的影响原树。 我们深知可能复现不了当时完整的情况，历史太过斑驳，可能的烟花组合成千上万，因此你只需要得到答案对 $998244353$ 这个大质数取模的值。

第一行两个整数 $n,p$，表示树的节点个数与限制个数。 接下来 $n-1$ 行，每行两个数 $u,v$，表示 $u,v$ 之间有一条直连边。这 $n-1$ 行表示树的结构。 接下来 $p$ 行，每行两个数 $(x_i,y_i)$，表示限制以 $x_i$ 点为根的子树，需要恰好存在 $y_i$ 个黑点在其子树内。 接下来一行一个整数 $q$，表示询问个数。 接下来 $q$ 行，每行一个字符另加 $1$ 或 $2$ 个整数表示题目中说明的询问。

为了减小输出量，我们假设第 $i$ 个询问（$i$ 从 $1$ 开始）的答案为 $ans_i$，你只需要输出一行，表示所有询问的 $i\times ans_i$ 的异或和。最终的异或和以及每一个 $i\times ans_i$ 都**无需**对 $998244353$ 取模，但每个询问的答案 $ans_i$ 是对其取模后的答案。 **注意：std 不依赖于输出方式。也就是说，std 可以独立获取每一个询问的答案。**

### 样例解释  如图为样例 #1 的烟花，构成一个有 $14$ 个点，其中 $5$ 个限制点的树。与题目中不同的是，我们用红色烟花表示限制点，蓝色烟花表示无限制点。红色烟花右上角的浅蓝色数字表示其限制的黑点数量。 初始情况下每一个点为根子树的合法烟花燃放方法数量如下（从左至右第 $i$ 项表示以第 $i$ 个点为根的子树的答案）： $$ [320,10,4,4,2,8,1,2,2,1,2,2,1,1] $$ 下面我们给出询问的答案与部分解释： - `Z 2 5`，为 $2$ 号点添加 $i$ 个儿子后的 $2$ 号点子树内合法烟花燃放数量表示为此数列的第 $i+1$ 项：$[10,20,35,56,84,120]$。总期望即为 $\frac{325}{6}$。对 $998244353$ 取模之后得到 $166374113$。 - `H 14`，由于 $14$ 号点没有儿子，因此答案仍然为 $1$。 - `Z 7 3`，共有 $10$ 种可能的合法烟花燃放方案，总期望即为 $\frac{5}{2}$，对 $998244353$ 取模之后得到 $499122179$。 - `Z 7 1` 的答案为 $499122178$。 - `H 6` 的答案为 $16$。 - `Z 1 9` 的答案为 $32736$。 - `H 1`，去除 $1$ 的所有有限制儿子（仅有节点 $2$）的限制后有 $1024$ 种可能的合法烟花燃放方案。 - `H 8` 的答案为 $8$。 - `H 12` 没有儿子，因此答案不变，此询问的答案仍然为 $2$。 - `Z 10 1` 的答案为 $1$。 最终，所有询问的 $i\times ans_i$ 的异或和即为 $665340330$。 ### 数据范围 **请注意常数因子对程序效率的影响。** **本题采用捆绑测试与子任务依赖。** 下面定义 $S=3\times 10^5$。 | $\rm Subtask$ | $n$ | $q$ | $y_i$ | $c$ | 特殊性质 | 得分 | 子任务依赖 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leqslant 10$ | $\leqslant 10$ | $\leqslant 5$ | $\leqslant 5$ | 无 | $10$ | 无 | | $2$ | $\leqslant 200$ | $\leqslant 200$ | $\leqslant 200$ | $\leqslant 200$ | 无 | $15$ | $1$ | | $3$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant 10$ | 无 | $20$ | $1,2$ | | $4$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $A$ | $15$ | 无 | | $5$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $B$ | $20$ | 无 | | $6$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | 无 | $20$ | $1,2,3,4,5$ | 特殊性质 $A$：$p=0$。 特殊性质 $B$：满足不存在 `Z` 询问。 对于 $100\%$ 的数据，存在输入的所有数均为 $\leqslant S$ 的整数。特别地，存在 $0\leqslant p\leqslant n$，输入的任何树的节点编号 $x$ 都满足 $1\leqslant x \leqslant n$。保证输入的询问字符都为 `Z` 或 `H`，输入的一定是一棵树。保证对于所有限制存在 $x_i\neq x_j(i\neq j)$。 ------------ 冬天的最后一场雪如约而至，很快又要迎来一个新的春天。万物都在等待复苏，可峰城里的一个小巷子，再也不复往日繁荣。 八十多年过去，我们早已找不到当初的巷子，只留下这样一个故事。 感谢你放的烟花。