{"problem":{"name":"[SNOI2024] 树 V 图","description":{"content":"你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \\ldots, n$。定义树上两点之间的距离 $\\operatorname{dis}(i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。 现在有 $k$ 个关键点 $a_1, a_2, \\ldots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\\op","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10060"},"statements":[{"statement_type":"Markdown","content":"你有一棵 $n$ 个点的无根树，节点的编号为 $1, 2, \\ldots, n$。定义树上两点之间的距离 $\\operatorname{dis}(i, j)$ 为树上 $i$ 点到 $j$ 点的简单路径上的边数。\n\n现在有 $k$ 个关键点 $a_1, a_2, \\ldots, a_k$，对于每个点，我们想求出距离它最近的关键点是哪个点。也就是对于一个点 $v$，令 $f(v)$ 表示令 $\\operatorname{dis}(v, a_i)$ 最小的 $i$，如果有多个 $i$ 满足条件，那么我们会选择其中最小的 $i$。\n\n现在，我们给出了 $f(1), f(2), \\ldots, f(n)$，问有多少组可能的 $(a_1, a_2, \\ldots, a_k)$ 满足条件。由于答案可能很大，输出对 $998244353$ 取模的结果。\n\n## Input\n\n多组测试数据，第一行一个整数 $T$ 表示数据组数。  \n对于每组测试数据，第一行两个整数 $n, k$，表示节点个数和关键点个数。  \n接下来 $n - 1$ 行，每行两个整数 $u, v$，表示一条树边 $(u, v)$。  \n接下来一行，$n$ 个整数，$f(1), f(2), \\ldots, f(n)$。注意：数据**不保证**一定存在一组可能的 $(a_1, a_2, \\ldots, a_k)$。\n\n## Output\n\n对于每组数据，输出一个整数，表示答案对 $998244353$ 取模的结果。\n\n[samples]\n\n## Note\n\n**【样例 \\#1 解释】**\n\n在第一个样例中，对于第二组数据，一个解为 $(1, 2)$。对于第三组数据，两个解为 $(2, 1), (3, 1)$。\n\n注意，当多个点距离相同时，我们选择的是最小的 $i$ 而不是 $a_i$。\n\n---\n\n**【样例 \\#3】**\n\n见附件中 `voronoi/voronoi3.in` 与 `voronoi/voronoi3.ans`，这个样例满足测试点 $3 \\sim 4$ 的条件限制。\n\n---\n\n**【样例 \\#4】**\n\n见附件中 `voronoi/voronoi3.in` 与 `voronoi/voronoi3.ans`，这个样例满足测试点 $7 \\sim 10$ 的条件限制。\n\n---\n\n**【数据范围】**\n\n对于所有的数据，保证 $1 \\le T \\le 10$，$2 \\le k \\le n \\le 3 \\times {10}^3$，$1 \\le f(i) \\le k$。\n\n具体如下：\n\n| 测试点编号 | $n \\le$ | 特殊性质 |\n|:-:|:-:|:-:|\n| $1 \\sim 2$ | $15$ | 无 |\n| $3 \\sim 4$ | $3000$ | A |\n| $5 \\sim 6$ | $3000$ | B |\n| $7 \\sim 10$ | $3000$ | 无 |\n\n特殊性质 A：保证树是一条链。  \n特殊性质 B：保证 $k = 2$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10060","tags":["各省省选","2024","O2优化","陕西"],"sample_group":[["3\n3 3\n1 2\n2 3\n1 2 1\n3 2\n1 2\n2 3\n1 2 2\n3 2\n1 2\n2 3\n2 1 1\n","0\n1\n2\n"],["1\n10 5\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n1 1 2 2 3 3 4 4 5 5\n","13\n"]],"created_at":"2026-03-03 11:09:25"}}