P10203 [Hubei NOI Qualifier Mock 2024] Toy Salesman / tartaglia

Childhood dreams are the easiest things to break. Even if you leave them alone, one day they will break by themselves. So there must be someone to protect them.

“One-Eyed Little Buddy” is Toke’s favorite toy. As the best toy salesman in Liyue, Tartaglia recruited $N$ dealers to distribute “One-Eyed Little Buddy”. The $N$ dealers are numbered $1,2,\cdots,N$ in order. Among the $N$ dealers, there are $M$ trading relationships in total, numbered $1,2,\cdots,M$ in order. The $i$-th trading relationship connects dealers $u_i$ and $v_i$. For the $i$-th trading relationship, when one side learns the production information of “One-Eyed Little Buddy”, it will tell the other side with probability $\dfrac{p_i}{q_i}$. Formally, the dealers and their trading relationships form an undirected graph. **The testdata guarantees that this undirected graph is connected, has no self-loops, and has no multiple edges.** Some dealers $a_1,a_2,\cdots,a_k(k>2)$ form a **business group** if and only if there exist $k$ distinct trading relationships such that the $w$-th relationship connects dealers $a_w$ and $a_{w \bmod k+1}$. Formally, a business group corresponds to $k$ dealers and a simple cycle in their trading-relationship graph. **A dealer belongs to at most one business group.** Now, Tartaglia wants to test these dealers. He performs $Q$ **independent** tests in total. In the $i$-th test, Tartaglia tells the production information of “One-Eyed Little Buddy” to dealer $S_i$. Under expectation, how many dealers will learn this information in total? **It can be proven that the expectation can always be written in the form $\dfrac{p}{q}$. You need to output the value of $p\cdot q^{-1}\pmod {998\ 244\ 353}$.**

The input has $M+Q+1$ lines. The first line contains three positive integers $N,M,Q$, representing the number of dealers, the number of trading relationships, and the number of tests. The next $M$ lines each contain four positive integers $u_i,v_i,p_i,q_i$, representing the dealers connected by the $i$-th trading relationship and the probability of telling. The next $Q$ lines each contain one integer $S_i$, representing the dealer who is told in the $i$-th test.

Output $Q$ lines. For each query, output one integer per line, representing the expected value modulo $998\ 244\ 353$.

### Sample Explanation 1     The figures above show all $16$ possible connectivity cases of the graph. From top to bottom and left to right, they are numbered $1\sim 16$ in order. For the query at node $1$, we compute, for each of the $16$ cases, the number of nodes reachable from node $1$ and the probability of that case: | Graph ID | Number of nodes | Probability | Expectation | | :--: | :--: | :--: | :--: | | $1$ | $4$ | $\frac{1}{60}$ | $\frac{1}{15}$ | | $2$ | $1$ | $\frac{1}{60}$ | $\frac{1}{60}$ | | $3$ | $4$ | $\frac{1}{30}$ | $\frac{2}{15}$ | | $4$ | $4$ | $\frac{1}{15}$ | $\frac{4}{15}$ | | $5$ | $4$ | $\frac{1}{60}$ | $\frac{1}{15}$ | | $6$ | $1$ | $\frac{1}{30}$ | $\frac{1}{30}$ | | $7$ | $1$ | $\frac{1}{15}$ | $\frac{1}{15}$ | | $8$ | $1$ | $\frac{1}{60}$ | $\frac{1}{60}$ | | $9$ | $3$ | $\frac{2}{15}$ | $\frac{2}{5}$ | | $10$ | $2$ | $\frac{1}{30}$ | $\frac{1}{15}$ | | $11$ | $3$ | $\frac{1}{15}$ | $\frac{1}{5}$ | | $12$ | $1$ | $\frac{2}{15}$ | $\frac{2}{15}$ | | $13$ | $1$ | $\frac{1}{30}$ | $\frac{1}{30}$ | | $14$ | $1$ | $\frac{1}{15}$ | $\frac{1}{15}$ | | $15$ | $2$ | $\frac{2}{15}$ | $\frac{4}{15}$ | | $16$ | $1$ | $\frac{2}{15}$ | $\frac{2}{15}$ | Summing up, we get $E=\sum E_i=\frac{59}{30}\equiv 565\ 671\ 802\pmod{998\ 244\ 353}$. ### Subtasks For all testdata, it is guaranteed that $1 \leq N,M,Q \leq 3 \times 10^5$, $1 \le u_i,v_i \le N$, $u_i\neq v_i$, $1 \le p_i,q_i < 998\ 244\ 353$, $1 \le S_i \le N$. | Test point ID | $N,M,Q\le$ | Special property | | :--: | :--: | :--: | | $1\sim 2$ | $17$ | None | | $3\sim 4$ | $2\times 10^3$ | A | | $5\sim 7$ | $2\times 10^3$ | B | | $8\sim 9$ | $2\times 10^3$ | None | | $10\sim 13$ | $3\times 10^5$ | A | | $14\sim 19$ | $3\times 10^5$ | B | | $20\sim 25$ | $3\times 10^5$ | None | Special property A: No groups exist. Special property B: There is one and only one group. ### Notes In this problem, you may need to use a larger stack space. In the final test, the stack space memory limit available to the program is the same as the problem’s memory limit. If you are using Linux, you can use the command `ulimit -s unlimited` to remove the system stack space limit. If you are using Windows, you can add `-Wl,--stack=1024000000` after the compile command to change the system stack space limit to about 1024 MiB. Translated by ChatGPT 5