P7498 Magnetic Control Rules

>That is nothing more than someone else’s misfortune. Norton entered a cave with a complex structure. From previous exploration, he already knew that the treasure he longed for was hidden in this cave. However, the cave was so dark and complicated that he searched for a long time without finding where the treasure was. Still, the strong attraction of the treasure drove him to keep searching. But soon he realized something was wrong, because that attraction acted not only in his mind but also on his body—the treasure’s defense mechanism was releasing a huge magnetic force to drive away intruders. “So, this is its built-in protection mechanism?” Norton smiled and took out a small piece of metal glowing with a strange light. “But I came prepared.”

The cave Norton is in can be viewed as a tree formed by $n$ chambers and $n-1$ passages. Norton is in chamber $s$, and the treasure is in chamber $t$. In the treasure chamber there is a special magnet with a powerful magnetic field, and Norton also carries a small magnet made of the same material. The magnet in the treasure chamber has **only one pole** (N or S), and **its pole never changes**. Norton’s magnet also has **only one pole** (N or S), but **at the start of each moment it switches poles with probability $p$** (N becomes S, S becomes N). At each moment, Norton’s movement is determined by the pole of the treasure-chamber magnet and the pole of Norton’s magnet: 1. The two magnets have different poles. In this case, the magnets trigger an “attraction” effect. Norton will move, due to the attractive force, to the chamber adjacent to $s$ whose distance to $t$ is $-1$ (that is, **the parent of $s$ when rooting the tree at $t$**). 2. The two magnets have the same pole. In this case, the magnets trigger a “bounce” effect. Norton will, due to the repulsive force, move **uniformly at random** to one of the chambers adjacent to $s$ whose distance to $t$ is $+1$ (that is, **any child of $s$ when rooting the tree at $t$**). If there is no such chamber, a “stun” effect is triggered: in the next moment, Norton will **not make any move, and will not perform any pole switching either**. After some investigation, Norton already knows the entire cave structure and the pole-switching probability $p$. To search for the treasure more effectively, each time he asks you a query: you need to answer, if initially Norton is in chamber $x$ with his magnet pole being $c_1$, and the treasure is in chamber $y$ with the chamber magnet pole being $c_2$, what is the expected number of moments until Norton can find the treasure.

The first line contains three integers $n,q,p$, representing the number of chambers, the number of queries, and the pole-switching probability. The pole-switching probability is given as a probability modulo $998244353$. The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is a passage between chambers $u$ and $v$. It is guaranteed that the final structure is a tree. The next $q$ lines each contain, **in order**, a positive integer $x$, a character $c_1$, a positive integer $y$, and a character $c_2$, indicating one query, with meanings as above. It is guaranteed that $c_1,c_2$ are `N` or `S`.

Output $q$ lines. Each line contains one non-negative integer, representing the query answer modulo $998244353$.

#### Explanation of Sample 1 The pole-switching probability at each moment is $\dfrac{1}{2}$. The cave structure is as follows:  For query 1, at moment $1$ Norton has probability $\dfrac{1}{2}$ to move to $1$, and probability $\dfrac{1}{2}$ to trigger “stun” and enter moment $3$. At moment $3$, similarly, he has probability $\dfrac{1}{2}$ to move to $1$, and probability $\dfrac{1}{2}$ to trigger “stun” and enter moment $5$... The expected value is $1\times\dfrac{1}{2}+3\times\left(\dfrac{1}{2}\right)^2+5\times\left(\dfrac{1}{2}\right)^3+\ldots=3$. ------------ #### Constraints **This problem uses bundled testdata.** + Subtask 1 ( $10\%$ ): $n,q\leq15$. + Subtask 2 ( $20\%$ ): $n\leq10^3$. + Subtask 3 ( $25\%$ ): For all queries, it is guaranteed that $y=1$. + Subtask 4 ( $45\%$ ): No special restrictions. For all testdata, $2\leq n\leq5\times 10^5,1\leq q\leq5\times10^5,1\leq u,v,x,y\leq n,x\neq y,2\leq p\leq998244352$. ------------ **The input size of this problem is large. Please use a fast input method.** Translated by ChatGPT 5