题目描述
Problem Description
Little S has a tree with $n$ nodes. Each node has a light bulb.
Little S decides to perform $k$ flash operations. During each flash operation, he sends a signal to each light bulb from his computer.
However, Little S's light bulbs are of poor quality, and only some of them can receive the flash signal from Little S. Specifically, the light bulb at node $j$ has a probability of $p_{i,j}$ to receive the $i$-th flash operation from Little S.
Fortunately, the light bulbs have a message transmission feature. Specifically, if a light bulb is on the shortest path between two light bulbs that received the signal, this light bulb can also perform the flash operation (of course, the light bulbs that received the signal will perform the flash operation).
Define the beauty of a light bulb $i$ as $a_{i,S}$, where $S$ is the set of operations for which this light bulb performs the flash operation.
Define the beauty of the entire tree as the product of the beauty of each light bulb. Calculate the expected beauty of the tree, modulo $998244353$.
Input Format
The first line contains two positive integers $n, k$, representing the number of nodes in the tree and the number of operations, respectively.
The next $n-1$ lines each contain two positive integers $u, v$, representing an edge in the tree between nodes $u$ and $v$.
The next $k$ lines each contain $n$ non-negative integers, where the $j$-th integer in the $i$-th line represents $p_{i,j}$ modulo $998244353$.
The next $n$ lines each contain $2^k$ non-negative integers, where the $(\sum_{i=1}^k2^{i-1}[i\in S])+1$-th integer in the $i$-th line represents $a_{i,S}$. This can be understood as the $x$-th binary digit from the least significant bit of $j-1$ representing whether there is an $x$ operation.
Output Format
One line containing a non-negative integer, representing the expected beauty of the tree, modulo $998244353$.
Sample Input and Output
Input Sample #1
3 1
1 2
2 3
499122177 499122177 499122177
1 2
1 3
1 4
Output Sample #1
499122186
Input Sample #2
10 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1 4 5
1 4 1 9
1 9 8 1
0 1 1 4
5 1 4 1
9 1 9 8
1 0 9 9
8 2 4 4
3 5 3 1
2 3 4 5
Output Sample #2
497209006
Notes
[Sample Explanation #1]
| Set of Light Bulbs Receiving Signal | Beauty of Light Bulbs | Tree Beauty |
|---|---|---|
| $\emptyset$ | $1,1,1$ | $1$ |
| $\{1\}$ | $2,1,1$ | $2$ |
| $\{2\}$ | $1,3,1$ | $3$ |
| $\{3\}$ | $1,1,4$ | $4$ |
| $\{1,2\}$ | $2,3,1$ | $6$ |
| $\{1,3\}$ | $2,3,4$ | $24$ |
| $\{2,3\}$ | $1,3,4$ | $12$ |
| $\{1,2,3\}$ | $2,3,4$ | $24$ |
Thus, the expected beauty is $\frac{1+2+3+4+6+24+12+24}{8}=\frac{19}{2}$, which modulo $998244353$ is $499122186$.
[Data Range]
This problem uses batched testing.
| Subtask Number | Score | $n\leq$ | $k\leq$ | Special Conditions |
|---|---|---|---|---|
| $1$ | $5$ | $20$ | $1$ | None |
| $2$ | $10$ | $100$ | $2$ | The $i$-th edge connects node $i$ and node $i+1$ |
| $3$ | $5$ | $100$ | $8$ | $p_{i,j}=0$ or $p_{i,j}=1$ |
| $4$ | $5$ | $100$ | $8$ | $a_{i,S}=[S=\{1,2,\dots,k\}]$ |
| $5$ | $20$ | $100$ | $8$ | The $i$-th edge connects node $i$ and node $i+1$ |
| $6$ | $15$ | $100$ | $6$ | None |
| $7$ | $15$ | $100$ | $7$ | None |
| $8$ | $10$ | $50$ | $8$ | None |
| $9$ | $15$ | $100$ | $8$ | None |
For $100\%$ of the data: $1\leq n\leq100$, $1\leq k\leq8$, $1\leq u,v\leq n$, the given data forms a tree, and all other input data are integers in the range $[0,998244353)$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分