{"problem":{"name":"[ZJOI2022] 深搜","description":{"content":"九条可怜是一个喜欢算法的女孩子，在众多算法中她尤其喜欢深度优先搜索（DFS）。 有一天，可怜得到了一棵有根树，树根为 $\\mathit{root}$，树上每个节点 $x$ 有一个权值 $a_x$。 在一棵树上从 $x$ 出发，寻找 $y$ 节点，如果使用深度优先搜索，则可描述为以下演算过程： 1. 将递归栈设置为空。 2. 首先将节点 $x$ 放入递归栈中。 3. 从递归栈中取出栈顶节点，如","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8334"},"statements":[{"statement_type":"Markdown","content":"九条可怜是一个喜欢算法的女孩子，在众多算法中她尤其喜欢深度优先搜索（DFS）。\n\n有一天，可怜得到了一棵有根树，树根为 $\\mathit{root}$，树上每个节点 $x$ 有一个权值 $a_x$。\n\n在一棵树上从 $x$ 出发，寻找 $y$ 节点，如果使用深度优先搜索，则可描述为以下演算过程：\n\n1. 将递归栈设置为空。\n2. 首先将节点 $x$ 放入递归栈中。\n3. 从递归栈中取出栈顶节点，如果该节点为 $y$，则结束演算过程；否则，如果存在未访问的直接子节点，则以均等概率随机选择一个子节点加入递归栈中。\n4. 重复步骤 3，直到不存在未访问的直接子节点。\n5. 将上一级节点加入递归栈中，重复步骤 3。\n6. 重复步骤 5，直至当前一级节点为 $x$，演算过程结束。\n\n我们定义 $f(x, y)$ 合法当且仅当 $y$ 在 $x$ 的子树中。它的值为从 $x$ 出发，对 $x$ 的子树进行深度优先搜索寻找 $y$ 期间访问过的所有节点（包括 $x$ 和 $y$）权值最小值的期望。\n\n九条可怜想知道对于所有合法的点对 $(x, y)$，$\\sum f(x, y)$ 的值。你只需要输出答案对 $998244353$ 取模的结果。具体地，如果答案的最简分数表示为 $\\frac{a}{b}$，输出 $a \\times b^{-1} \\bmod 998244353$。\n\n## Input\n\n输入包含多组数据，第一行输入数据组数 $T$。\n\n对于接下来的每组数据，第一行两个整数 $n, \\mathit{root}$，分别表示树的大小，树根的编号。\n\n接下来一行 $n$ 个整数 $a_1, a_2, \\ldots, a_n$，表示树上每个节点的权值。\n\n接下来 $n - 1$ 行，每行包含两个整数 $u, v$，表示 $u$ 和 $v$ 之间有一条树边。\n\n## Output\n\n对于每组数据，输出一行，包含一个整数，代表对于所有合法点对 $(x, y)$，$\\sum f(x, y)$ 对 $998244353$ 取模的结果。\n\n[samples]\n\n## Note\n\n对于所有测试点，满足 $1 \\le T \\le 100$，$\\sum n \\le 8 \\times {10}^5$，$1 \\le n \\le 4 \\times {10}^5$，$1 \\le \\mathit{root}, u, v \\le n$，$1 \\le a_i \\le {10}^9$。\n\n每个测试点的具体限制见下表：\n\n| 测试点编号 | $\\sum n \\le$ | $n \\le$ | 特殊限制 |\n|:-:|:-:|:-:|:-:|\n| $1$ | $50$ | $10$ | 无 |\n| $2 \\sim 4$ | $40000$ | $5000$ | 无 |\n| $5 \\sim 10$ | $4 \\times {10}^5$ | ${10}^5$ | 无 |\n| $11$ | $8 \\times {10}^5$ | $4 \\times {10}^5$ | 树的生成方式随机 |\n| $12$ | $8 \\times {10}^5$ | $4 \\times {10}^5$ | 树是一条链 |\n| $13$ | $8 \\times {10}^5$ | $4 \\times {10}^5$ | 根的度数为 $n - 1$ |\n| $14 \\sim 20$ | $8 \\times {10}^5$ | $4 \\times {10}^5$ | 无 |\n\n对于测试点 $11$，树的生成方式为：以 $1$ 为根，对于节点 $i \\in [2, n]$，从 $[1, i - 1]$ 中等概率随机选\n择一个点作为父亲。之后将编号随机重排。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8334","tags":["动态规划 DP","线段树","各省省选","2022","浙江","O2优化","树链剖分","矩阵乘法"],"sample_group":[["4\n1 1\n1\n3 3\n3 3 4\n3 1\n3 2\n6 1\n5 2 4 1 3 6\n1 2\n1 6\n2 3\n2 4\n4 5\n5 1\n5 4 3 2 1\n1 2\n1 3\n3 4\n3 5\n","1\n16\n34\n499122202\n"],["见附件中的 dfs/dfs_ex2.in","见附件中的 dfs/dfs_ex2.ans"]],"created_at":"2026-03-03 11:09:25"}}