P9398 "DBOI" Round 1 Fireworks

Memory itself is a punishment, punishing those who are unwilling to move forward, trapping them in that little alley, unable to ever get out. There are fireworks every year, but only the fireworks of that year were the most beautiful. "I want to make a wish to the fireworks, to wish that we will always be together." "Even if you don't make a wish, we will always be together." Later on, the dead were buried on that mountain, and the living were trapped in that alley by memories. Today, when we hear this story, we only want to set off the fireworks from the story one more time, for those who never got to watch fireworks once more with the person beside them.

Fireworks bloom in the night sky and connect into one whole scene. We view these connected fireworks as a rooted tree with $n$ nodes, where the root is the earliest lit firework $1$. Fireworks have two colors, red and blue. For convenience, we color this tree in black and white. Initially there are $p$ constraints. Each constraint has the form $(x_i,y_i)$, meaning that in the subtree of node $x_i$, the number of black nodes must be **exactly** $y_i$. Back then, they called a subtree that satisfies **all constraints of all constrained nodes inside its subtree** a **balanced-good subtree**. Clearly, to make a subtree a balanced-good subtree, there may be **multiple coloring methods**. You need to answer the following two types of queries: - `Z k c`: For node $k$, choose a number $f$ uniformly at random from $[0,c]$, then directly add $f$ unconstrained children to node $k$, keeping all other children unchanged. Ask for the expected number of coloring methods that make the subtree rooted at $k$ a **balanced-good subtree**. - `H k`: Remove the constraints of all constrained children of $k$, and ask for the number of coloring methods that make the subtree rooted at $k$ a **balanced-good subtree**. We do not need to light more fireworks, so all queries are independent of each other; no query will actually modify the original tree. We know that we may not be able to fully reproduce what happened back then. History is too fragmented, and the possible firework combinations are countless. Therefore, you only need the answer modulo the large prime $998244353$.

The first line contains two integers $n,p$, representing the number of nodes in the tree and the number of constraints. The next $n-1$ lines each contain two numbers $u,v$, indicating that there is a direct edge between $u$ and $v$. These $n-1$ lines describe the structure of the tree. The next $p$ lines each contain two numbers $(x_i,y_i)$, indicating a constraint: in the subtree rooted at node $x_i$, there must be exactly $y_i$ black nodes in its subtree. The next line contains an integer $q$, representing the number of queries. The next $q$ lines each contain one character plus $1$ or $2$ integers, representing the queries described in the statement.

To reduce the output size, suppose the answer to the $i$-th query (with $i$ starting from $1$) is $ans_i$. You only need to output one line: the xor-sum of all $i\times ans_i$. The final xor-sum and each $i\times ans_i$ do **not** need to be taken modulo $998244353$, but each query answer $ans_i$ is the value after taking modulo $998244353$. **Note: the standard solution does not depend on the output method. That is, the standard solution can obtain the answer to each query independently.**

### Sample Explanation  As shown in the figure, the fireworks of Sample #1 form a tree with $14$ nodes, among which $5$ are constrained nodes. Different from the statement, we use red fireworks to represent constrained nodes, and blue fireworks to represent unconstrained nodes. The light-blue number at the top-right of a red firework indicates the required number of black nodes. Initially, the number of valid firework-lighting methods for the subtree rooted at each node is as follows (from left to right, the $i$-th item is the answer for the subtree rooted at node $i$): $$ [320,10,4,4,2,8,1,2,2,1,2,2,1,1] $$ Below we give the query answers and some explanations: - `Z 2 5`: After adding $i$ children to node $2$, the number of valid firework-lighting methods in the subtree of node $2$ is the $(i+1)$-th term of this sequence: $[10,20,35,56,84,120]$. The total expectation is $\frac{325}{6}$. Modulo $998244353$, it is $166374113$. - `H 14`: Since node $14$ has no children, the answer is still $1$. - `Z 7 3`: There are $10$ possible valid firework-lighting plans in total, so the expectation is $\frac{5}{2}$. Modulo $998244353$, it is $499122179$. - The answer to `Z 7 1` is $499122178$. - The answer to `H 6` is $16$. - The answer to `Z 1 9` is $32736$. - `H 1`: After removing the constraints of all constrained children of $1$ (only node $2$), there are $1024$ possible valid firework-lighting plans. - The answer to `H 8` is $8$. - `H 12`: It has no children, so the answer does not change; it is still $2$. - The answer to `Z 10 1` is $1$. Finally, the xor-sum of all $i\times ans_i$ is $665340330$. ### Constraints **Please pay attention to the impact of constant factors on program efficiency.** **This problem uses bundled tests and subtask dependencies.** Let $S=3\times 10^5$. | $\rm Subtask$ | $n$ | $q$ | $y_i$ | $c$ | Special Property | Score | Dependencies | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $\leqslant 10$ | $\leqslant 10$ | $\leqslant 5$ | $\leqslant 5$ | None | $10$ | None | | $2$ | $\leqslant 200$ | $\leqslant 200$ | $\leqslant 200$ | $\leqslant 200$ | None | $15$ | $1$ | | $3$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant 10$ | None | $20$ | $1,2$ | | $4$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $A$ | $15$ | None | | $5$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $B$ | $20$ | None | | $6$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | $\leqslant S$ | None | $20$ | $1,2,3,4,5$ | Special property $A$: $p=0$. Special property $B$: there are no `Z` queries. For $100\%$ of the data, all input numbers are integers $\leqslant S$. In particular, $0\leqslant p\leqslant n$, and every node index $x$ in the input satisfies $1\leqslant x \leqslant n$. It is guaranteed that each query character is either `Z` or `H`, the input is a tree, and for all constraints we have $x_i\neq x_j(i\neq j)$. ------------ The last snow of winter arrived as promised, and soon a new spring will come. Everything is waiting to wake up again, but the little alley in Fengcheng will never return to its former prosperity. More than eighty years have passed. We can no longer find the alley from back then, leaving only this story. Thank you for the fireworks you set off. Translated by ChatGPT 5