P5575 [CmdOI2019] Black and White Graph

You saw a strange graph.

There is a simple undirected connected graph with $n$ vertices and $m$ edges. Each vertex can be colored black or white. This graph is relatively sparse. Specifically, there are two cases. - $m=n-1$, in which case it is a tree. - $m=n$, in which case it is a unicyclic graph (a tree with one extra edge). We define the value of a black-and-white graph as follows: the sum of the $k$-th powers of the sizes of its black connected components. Now the shape of the graph is fixed, but the color of each vertex is not fixed. For the $i$-th vertex, it has a probability of **$p_i$ percent** to be black; otherwise it is white. Compute the expected value of the graph, modulo $998244353$.

The first line contains three positive integers $n,m,k$, with meanings as described above. The next line contains $n$ numbers, which are $p_{1\sim n}$ in order. The next $m$ lines each contain two numbers $f,t$, indicating an undirected edge $f\leftrightarrow t$ in the graph.

Output one integer, the expected value of the graph modulo $998244353$.

| Test Point ID | $n$ | 　$m$　 | 　$k$　 | Property 1 | Property 2 | Score | | :--: | :--: | :--: | :--: | :--: | :--: | :--: | | 1 | $16$ | $n-1$ | $5$ | $\sqrt{}$ | - | $5$ | | 2 | $50$ | $n-1$ | $3$ | $\sqrt{}$ | $\sqrt{}$ | $5$ | | 3 | $50$ | $n-1$ | $5$ | $\sqrt{}$ | - | $5$ | | 4 | $500$ | $n-1$ | $1$ | - | - | $5$ | | 5 | $2\times 10^5$ | $n-1$ | $3$ | $\sqrt{}$ | $\sqrt{}$ | $5$ | | 6 | $2\times 10^5$ | $n-1$ | $2$ | - | $\sqrt{}$ | $5$ | | 7 | $2\times 10^5$ | $n-1$ | $4$ | - | - | $10$ | | 8 | $16$ | $n$ | $3$ | - | - | $10$ | | 9 | $500$ | $n$ | $3$ | - | - | $10$ | | 10 | $50000$ | $n$ | $2$ | - | - | $10$ | | 11 | $2\times 10^5$ | $n$ | $4$ | $\sqrt{}$ | - | $10$ | | 12 | $2\times 10^5$ | $n$ | $5$ | - | - | $10$ | | 13 | $2\times 10^5$ | $n$ | $5$ | - | - | $10$ | Special Property $1$: $p_i=50$. Special Property $2$: The graph degenerates into a single chain, where there is an edge between $i$ and $i+1$. Translated by ChatGPT 5