【MX-X1-T5】「KDOI-05」简单的树上问题

小 S 有一棵 $n$ 个点的树。每个点上有一个灯泡。 小 S 决定进行 $k$ 次闪灯操作。执行闪灯操作时，他会用电脑主机给每个灯泡发送一次闪灯操作。 然而，小 S 的灯泡是劣质品，只有一部分的灯泡可以收到小 S 的闪灯操作。具体地，第 $j$ 个点上的灯泡有 $p_{i,j}$ 的概率收到小 S 的第 $i$ 次闪灯操作。 好在，小 S 的不同灯泡之间有信息传递功能。具体地，如果一个灯泡在两个收到信息的灯泡的树上最短路径上，这个灯泡也能执行闪灯操作（当然，收到信息的灯泡会执行闪灯操作）。 定义一个灯泡 $i$ 的美丽度为 $a_{i,S}$，其中 $S$ 为这个灯泡执行闪灯操作的操作集合。 定义整棵树的美丽度为每个灯泡美丽度的乘积。求整棵树美丽度的期望，对 $998244353$ 取模。

第一行两个正整数 $n,k$，表示树的点数与操作次数。 接下来 $n-1$ 行每行两个正整数 $u,v$，表示树上的一条边 $(u,v)$。 接下来 $k$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个表示 $p_{i,j}$ 对 $998244353$ 取模后的值。 接下来 $n$ 行每行 $2^k$ 个非负整数，第 $i$ 行第 $(\sum_{i=1}^k2^{i-1}[i\in S])+1$ 个表示 $a_{i,S}$。可以理解为 $a_{i,j}$ 中 $j-1$ 的从低到高第 $x$ 个二进制位代表是否有 $x$ 操作。

一行，一个非负整数，表示整棵树的美丽度的期望，对 $998244353$ 取模。

3 1
1 2
2 3
499122177 499122177 499122177
1 2
1 3
1 4

499122186

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

497209006

**【样例解释 \#1】** | 收到信息灯泡集合 | 灯泡美丽度 | 树美丽度 | |:--:|:--:|:--:| | $\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$ | 故美丽度的期望是 $\frac{1+2+3+4+6+24+12+24}{8}=\frac{19}{2}$，对 $998244353$ 取模后为 $499122186$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n\leq$ | $k\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:|:--:| | $1$ | $5$ | $20$ | $1$ | 无 | | $2$ | $10$ | $100$ | $2$ | 第 $i$ 条边连接 $i$ 与 $i+1$ 号节点 | | $3$ | $5$ | $100$ | $8$ | $p_{i,j}=0$ 或 $p_{i,j}=1$ | | $4$ | $5$ | $100$ | $8$ | $a_{i,S}=[S=\{1,2,\dots,k\}]$ | | $5$ | $20$ | $100$ | $8$ | 第 $i$ 条边连接 $i$ 与 $i+1$ 号节点 | | $6$ | $15$ | $100$ | $6$ | 无 | | $7$ | $15$ | $100$ | $7$ | 无 | | $8$ | $10$ | $50$ | $8$ | 无 | | $9$ | $15$ | $100$ | $8$ | 无 | 对于 $100\%$ 的数据：$1\leq n\leq100$，$1\leq k\leq8$，$1\leq u,v\leq n$，保证给出数据为一棵树，保证其他输入数据均为 $[0,998244353)$ 中的整数。