[集训队互测 2023] 超现实树

Luogu

IDLGP10006

Time1000ms

Memory512MB

DifficultyP7

点分治集训队互测2023O2优化快速数论变换 NTT根号分治

Alek 认为，对于常数 $k$，一个字符串被称为「$k$-超现实数串」，如果其只包含字符 $\texttt{\{}, \texttt{|}, \texttt{\}}$，且： - 空串为 $k$-超现实数串； - 如果 $s, t$ 为 $k$-超现实数串，那么 $s + t$ 为 $k$-超现实数串； - 如果 $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$-超现实数串； - $k$-超现实数串仅限于此。给定一棵 $n$ 个点的无根树，节点编号为 $1 \sim n$。每个点 $i$ 上有一个字符 $a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$。给定整数 $m$，Alek 希望你对 $k = 0, 1, \cdots, m$ 分别求出：有多少有序对 $(x, y)$，$1 \leq x, y \leq n$，使得树上从点 $x$ 到点 $y$ 的唯一简单路径上的字符依次拼接所得字符串是 $k$-超现实数串。 ## Input 第一行两个整数 $n, m$，分别表示树的节点数，和需要求答案的 $k$ 的上限。第二行一个字符串 $a$，$a$ 的第 $i$ 个字符表示点 $i$ 上的字符。接下来 $n - 1$ 行，每行两个整数 $x, y$，表示存在一条连接点 $x$ 和点 $y$ 的边。 ## Output 输出一行 $m + 1$ 个整数，分别表示 $k = 0, 1, \cdots, m$ 时的答案。 [samples] ## Background Alek 喜欢打信息竞赛，尤其喜欢超现实树。超现实树，顾名思义，就是树上的超现实数。 ## Note 对于所有数据，有 $2 \leq n \leq 10^5$，$0 \leq m \leq n - 2$，$a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$。 - **Subtask 1**（5 分）：$n \leq 4601$； - **Subtask 2**（20 分）：对每条边 $(x, y)$ 有 $y = x + 1$； - **Subtask 3**（5 分）：$a_i \neq \texttt{|}$, $m = 0$； - **Subtask 4**（15 分，依赖 Subtask 3）：$m \leq 3$； - **Subtask 5**（25 分，依赖 Subtask 1）：$n \leq 5 \times 10^4$； - **Subtask 6**（30 分，依赖 Subtask 1, 2, 3, 4, 5）：无特殊限制。

Samples

Input #1

Output #1

1 2 0 0

Input #2

Output #2

2 0 1 1 0 0 0 0 0

Input #3

见附加文件 ex_surreal3.in。

Output #3

见附加文件 ex_surreal3.ans。

API Response (JSON)

{
  "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}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments