{"problem":{"name":"[集训队互测 2023] 超现实树","description":{"content":"Alek 认为，对于常数 $k$，一个字符串被称为「$k$-超现实数串」，如果其只包含字符 $\\texttt{\\{}, \\texttt{|}, \\texttt{\\}}$，且： - 空串为 $k$-超现实数串； - 如果 $s, t$ 为 $k$-超现实数串，那么 $s + t$ 为 $k$-超现实数串； - 如果 $k + 1$ 个字符串 $s_1, s_2, \\cdots, s_{k + 1}","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10006"},"statements":[{"statement_type":"Markdown","content":"Alek 认为，对于常数 $k$，一个字符串被称为「$k$-超现实数串」，如果其只包含字符 $\\texttt{\\{}, \\texttt{|}, \\texttt{\\}}$，且：\n\n- 空串为 $k$-超现实数串；\n- 如果 $s, t$ 为 $k$-超现实数串，那么 $s + t$ 为 $k$-超现实数串；\n- 如果 $k + 1$ 个字符串 $s_1, s_2, \\cdots, s_{k + 1}$ 都是 $k$-超现实数串，那么 $\\texttt{\\{} + s_1 + \\texttt{|} + s_2 + \\texttt{|} + \\cdots + \\texttt{|} + s_{k + 1} + \\texttt{\\}}$ 为 $k$-超现实数串；\n- $k$-超现实数串仅限于此。\n\n给定一棵 $n$ 个点的无根树，节点编号为 $1 \\sim n$。每个点 $i$ 上有一个字符 $a_i \\in \\{\\texttt{\\{}, \\texttt{|}, \\texttt{\\}}\\}$。\n\n给定整数 $m$，Alek 希望你对 $k = 0, 1, \\cdots, m$ 分别求出：有多少有序对 $(x, y)$，$1 \\leq x, y \\leq n$，使得树上从点 $x$ 到点 $y$ 的唯一简单路径上的字符依次拼接所得字符串是 $k$-超现实数串。\n\n## Input\n\n第一行两个整数 $n, m$，分别表示树的节点数，和需要求答案的 $k$ 的上限。\n\n第二行一个字符串 $a$，$a$ 的第 $i$ 个字符表示点 $i$ 上的字符。\n\n接下来 $n - 1$ 行，每行两个整数 $x, y$，表示存在一条连接点 $x$ 和点 $y$ 的边。\n\n## Output\n\n输出一行 $m + 1$ 个整数，分别表示 $k = 0, 1, \\cdots, m$ 时的答案。\n\n[samples]\n\n## Background\n\nAlek 喜欢打信息竞赛，尤其喜欢超现实树。超现实树，顾名思义，就是树上的超现实数。\n\n## Note\n\n对于所有数据，有 $2 \\leq n \\leq 10^5$，$0 \\leq m \\leq n - 2$，$a_i \\in \\{\\texttt{\\{}, \\texttt{|}, \\texttt{\\}}\\}$。\n\n- **Subtask 1**（5 分）：$n \\leq 4601$；\n- **Subtask 2**（20 分）：对每条边 $(x, y)$ 有 $y = x + 1$；\n- **Subtask 3**（5 分）：$a_i \\neq \\texttt{|}$, $m = 0$；\n- **Subtask 4**（15 分，依赖 Subtask 3）：$m \\leq 3$；\n- **Subtask 5**（25 分，依赖 Subtask 1）：$n \\leq 5 \\times 10^4$；\n- **Subtask 6**（30 分，依赖 Subtask 1, 2, 3, 4, 5）：无特殊限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10006","tags":["点分治","集训队互测","2023","O2优化","快速数论变换 NTT","根号分治"],"sample_group":[["5 3\n|{}}}\n2 1\n3 2\n4 1\n5 1","1 2 0 0"],["10 8\n|}||}{|{{{\n2 1\n3 1\n4 3\n5 2\n6 5\n7 5\n8 4\n9 2\n10 3","2 0 1 1 0 0 0 0 0"],["见附加文件 ex_surreal3.in。","见附加文件 ex_surreal3.ans。"]],"created_at":"2026-03-03 11:09:25"}}