{"problem":{"name":"【MX-X1-T5】「KDOI-05」简单的树上问题","description":{"content":"小 S 有一棵 $n$ 个点的树。每个点上有一个灯泡。 小 S 决定进行 $k$ 次闪灯操作。执行闪灯操作时，他会用电脑主机给每个灯泡发送一次闪灯操作。 然而，小 S 的灯泡是劣质品，只有一部分的灯泡可以收到小 S 的闪灯操作。具体地，第 $j$ 个点上的灯泡有 $p_{i,j}$ 的概率收到小 S 的第 $i$ 次闪灯操作。 好在，小 S 的不同灯泡之间有信息传递功能。具体地，如果一个灯泡","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10717"},"statements":[{"statement_type":"Markdown","content":"小 S 有一棵 $n$ 个点的树。每个点上有一个灯泡。\n\n小 S 决定进行 $k$ 次闪灯操作。执行闪灯操作时，他会用电脑主机给每个灯泡发送一次闪灯操作。\n\n然而，小 S 的灯泡是劣质品，只有一部分的灯泡可以收到小 S 的闪灯操作。具体地，第 $j$ 个点上的灯泡有 $p_{i,j}$ 的概率收到小 S 的第 $i$ 次闪灯操作。\n\n好在，小 S 的不同灯泡之间有信息传递功能。具体地，如果一个灯泡在两个收到信息的灯泡的树上最短路径上，这个灯泡也能执行闪灯操作（当然，收到信息的灯泡会执行闪灯操作）。\n\n定义一个灯泡 $i$ 的美丽度为 $a_{i,S}$，其中 $S$ 为这个灯泡执行闪灯操作的操作集合。\n\n定义整棵树的美丽度为每个灯泡美丽度的乘积。求整棵树美丽度的期望，对 $998244353$ 取模。\n\n## Input\n\n第一行两个正整数 $n,k$，表示树的点数与操作次数。\n\n接下来 $n-1$ 行每行两个正整数 $u,v$，表示树上的一条边 $(u,v)$。\n\n接下来 $k$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个表示 $p_{i,j}$ 对 $998244353$ 取模后的值。\n\n接下来 $n$ 行每行 $2^k$ 个非负整数，第 $i$ 行第 $(\\sum_{i=1}^k2^{i-1}[i\\in S])+1$ 个表示 $a_{i,S}$。可以理解为 $a_{i,j}$ 中 $j-1$ 的从低到高第 $x$ 个二进制位代表是否有 $x$ 操作。\n\n## Output\n\n一行，一个非负整数，表示整棵树的美丽度的期望，对 $998244353$ 取模。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/X1E>。\n\n## Note\n\n**【样例解释 \\#1】**\n\n::cute-table\n\n| 收到信息灯泡集合 | 灯泡美丽度 | 树美丽度 |\n|:--:|:--:|:--:|\n| $\\varnothing$ | $1,1,1$ | $1$ |\n| $\\{1\\}$ | $2,1,1$ | $2$ |\n| $\\{2\\}$ | $1,3,1$ | $3$ |\n| $\\{3\\}$ | $1,1,4$ | $4$ |\n| $\\{1,2\\}$ | $2,3,1$ | $6$ |\n| $\\{1,3\\}$ | $2,3,4$ | $24$ |\n| $\\{2,3\\}$ | $1,3,4$ | $12$ |\n| $\\{1,2,3\\}$ | $2,3,4$ | $24$ |\n\n故美丽度的期望是 $\\frac{1+2+3+4+6+24+12+24}{8}=\\frac{19}{2}$，对 $998244353$ 取模后为 $499122186$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n::cute-table{tuack}\n\n| 子任务编号 | 分值 | $n\\leq$ | $k\\leq$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|:--:|\n| $1$ | $5$ | $20$ | $1$ | 无 |\n| $2$ | $10$ | $100$ | $2$ | 第 $i$ 条边连接 $i$ 与 $i+1$ 号节点 |\n| $3$ | $5$ | $100$ | $8$ | $p_{i,j}=0$ 或 $p_{i,j}=1$ |\n| $4$ | $5$ | $100$ | $8$ | $a_{i,S}=[S=\\{1,2,\\dots,k\\}]$ |\n| $5$ | $20$ | $100$ | $8$ | 第 $i$ 条边连接 $i$ 与 $i+1$ 号节点 |\n| $6$ | $15$ | $100$ | $6$ | 无 |\n| $7$ | $15$ | $100$ | $7$ | 无 |\n| $8$ | $10$ | $50$ | $8$ | 无 |\n| $9$ | $15$ | $100$ | $8$ | 无 |\n\n对于 $100\\%$ 的数据：$1\\leq n\\leq100$，$1\\leq k\\leq8$，$1\\leq u,v\\leq n$，保证给出数据为一棵树，保证其他输入数据均为 $[0,998244353)$ 中的整数。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10717","tags":["O2优化","容斥原理","快速沃尔什变换 FWT","状压 DP","梦熊比赛"],"sample_group":[["3 1\n1 2\n2 3\n499122177 499122177 499122177\n1 2\n1 3\n1 4","499122186"],["10 2\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n1 2 3 4 5 6 7 8 9 10\n10 9 8 7 6 5 4 3 2 1\n1 1 4 5\n1 4 1 9\n1 9 8 1\n0 1 1 4\n5 1 4 1\n9 1 9 8\n1 0 9 9\n8 2 4 4\n3 5 3 1\n2 3 4 5","497209006"]],"created_at":"2026-03-03 11:09:25"}}