Background

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

Problem Description

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.

Input Format

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 Format

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

5 3
|{}}}
2 1
3 2
4 1
5 1

1 2 0 0

10 8
|}||}{|{{{
2 1
3 1
4 3
5 2
6 5
7 5
8 4
9 2
10 3

2 0 1 1 0 0 0 0 0

见附加文件 ex_surreal3.in。

见附加文件 ex_surreal3.ans。

Hint

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