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

原题链接：。

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

无

无

**【样例解释 \#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)$ 中的整数。