P4255 Princess’s #18 Civilization Game

The princess found a game priced at 998, so I paid to buy it for her (facepalm).

This game is called “Civil♂ization” (just for laughs), but it’s not the same as the usual meaning. There are $n$ cities in the game, numbered $1 \sim n$, connected by $m$ undirected roads, numbered $1 \sim m$. The system may add $N_i$ people to a city $X_i$, and assign these people the belief $C_i$. The system may also cut a road, given by its road ID $X_i$. The system may also give a city $X_i$ and ask: among all cities reachable from $X_i$, if we select $N_i$ people, what is the probability that all of them have belief $C_i$, modulo $19260817$. The input data are not guaranteed to be free of multiple edges and self-loops. The input data are not guaranteed that the same edge will not be cut more than twice. Because it is the princess’s game, the input size is large. Please optimize input/output.

The first line contains three positive integers $n, m, q$. The next $n$ lines each contain two positive integers $N_i, C_i$, representing the initial population and belief of city $i$. The next $m$ lines each contain two positive integers $X_i, Y_i$, representing the endpoints of a road. The next $q$ lines each begin with a positive integer $opt$ $(1 \leq opt \leq 3)$. - If $opt = 1$, the system adds people: input three integers $X_i, N_i, C_i$. - If $opt = 2$, the system cuts a road: input one integer $X_i$. - If $opt = 3$, the system asks for a probability: input three integers $X_i, N_i, C_i$.

For each operation with $opt = 3$, output one line with one integer.

Complaining that someone didn’t tell me I forgot to include a sample. Supplementing a sample (I actually had one). Apologies to everyone. Constraints: - For $30\%$ of the testdata, $1 \leq n, m, q \leq 100$. - For $60\%$ of the testdata, $1 \leq n, m, q \leq 50000$. - For $100\%$ of the testdata, $1 \leq n, m, q \leq 400000$. - For $100\%$ of the testdata, all beliefs fit within C++ int and Pascal long int. - For $100\%$ of the testdata, each addition size and each initial population do not exceed $10$. - For $100\%$ of the testdata, the testdata are randomly generated. Problem by @玫葵之蝶. Translated by ChatGPT 5