P10006 [CTT Mutual Test 2023] Surreal Tree

Alek likes competitive programming, and especially likes surreal trees. A surreal tree, as the name suggests, is a tree with surreal numbers on it.

Alek thinks that, for a constant $k$, a string is called a “$k$-surreal number string” if it contains only the characters $\texttt{\{}, \texttt{|}, \texttt{\}}$, and: - The empty string is a $k$-surreal number string. - If $s, t$ are $k$-surreal number strings, then $s + t$ is a $k$-surreal number string. - If $k + 1$ strings $s_1, s_2, \cdots, s_{k + 1}$ are all $k$-surreal number strings, then $\texttt{\{} + s_1 + \texttt{|} + s_2 + \texttt{|} + \cdots + \texttt{|} + s_{k + 1} + \texttt{\}}$ is a $k$-surreal number string. - $k$-surreal number strings are only those described above. You are given an unrooted tree with $n$ nodes, numbered $1 \sim n$. Each node $i$ has a character $a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$. Given an integer $m$, for each $k = 0, 1, \cdots, m$, Alek wants you to compute: how many ordered pairs $(x, y)$ with $1 \leq x, y \leq n$ are such that the string obtained by concatenating, in order, the characters along the unique simple path from node $x$ to node $y$ is a $k$-surreal number string.

The first line contains two integers $n, m$, representing the number of nodes in the tree, and the upper limit of $k$ for which you need to compute answers. The second line contains a string $a$, where the $i$-th character of $a$ is the character on node $i$. The next $n - 1$ lines each contain two integers $x, y$, indicating that there is an edge connecting node $x$ and node $y$.

Output one line with $m + 1$ integers, representing the answers for $k = 0, 1, \cdots, m$, respectively.

For all testdata, $2 \leq n \leq 10^5$, $0 \leq m \leq n - 2$, $a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}$. - **Subtask 1** (5 points): $n \leq 4601$. - **Subtask 2** (20 points): For every edge $(x, y)$, $y = x + 1$. - **Subtask 3** (5 points): $a_i \neq \texttt{|}$, $m = 0$. - **Subtask 4** (15 points, depends on Subtask 3): $m \leq 3$. - **Subtask 5** (25 points, depends on Subtask 1): $n \leq 5 \times 10^4$. - **Subtask 6** (30 points, depends on Subtask 1, 2, 3, 4, 5): No special constraints. Translated by ChatGPT 5