Background

Alek loves competitive programming, especially surreal trees. As the name suggests, surreal trees are surreal numbers on trees.

Problem Description

Alek believes that for a constant \( k \), a string is called a " \( k \)-surreal number string" if it only contains the characters {, |, and }, and:

• The empty string is a \( k \)-surreal number string;
• If \( s \) and \( 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 { + \( s_1 \) + | + \( s_2 \) + | + \cdots + | + \( s_{k + 1} \) + } is a \( k \)-surreal number string;
• \( k \)-surreal number strings are limited to these.

Given an \( n \)-node tree with no root, where the nodes are numbered from 1 to \( n \). Each node \( i \) has a character \( a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\} \).

Given an integer \( m \), Alek wants you to find for \( k = 0, 1, \cdots, m \) respectively: how many ordered pairs \( (x, y) \) with \( 1 \leq x, y \leq n \) exist such that the string formed by concatenating the characters on 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 \) and \( m \), representing the number of nodes in the tree and the upper limit of \( k \) for which answers are needed, respectively.

The second line contains a string \( a \), where the \( i \)-th character of \( a \) represents the character on node \( i \).

The next \( n - 1 \) lines each contain two integers \( x \) and \( 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.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1 2 0 0

Sample Input #2

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

Sample Output #2

2 0 1 1 0 0 0 0 0

Sample Input #3

See the attached file ex_surreal3.in.

Sample Output #3

See the attached file ex_surreal3.ans.

Notes

For all data, \( 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 each 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 Subtasks 1, 2, 3, 4, 5): No additional constraints.

见题面 Input 部分

见题面 Output 部分