Counting k‐Super‐Real Numeral Strings on Tree Paths

A string is called a \(k\)-super-real numeral string for a fixed constant \(k\) if it consists only of the characters {, |, and } and is generated by the following rules:

• The empty string is a \(k\)-super-real numeral string.
• If s and t are \(k\)-super-real numeral strings then their concatenation s+t is also a \(k\)-super-real numeral string.
• If \(s_1, s_2, \ldots, s_{k+1}\) are \(k\)-super-real numeral strings then
  \( \{\,s_1\,|\,s_2\,|\,\cdots\,|\,s_{k+1}\}\,\) is a \(k\)-super-real numeral string. \)
• No other strings are considered \(k\)-super-real numeral strings.

You are given an unrooted tree with \(n\) nodes, numbered from \(1\) to \(n\). Each node \(i\) contains a character \(a_i\) where \(a_i \in \{ {, |, } \}\). You are also given an integer \(m\). For each \(k = 0, 1, \ldots, m\), you must count the number of ordered pairs \((x,y)\) with \(1 \le x,y \le n\) such that the unique simple path in the tree from node \(x\) to node \(y\) (when the characters on the nodes are concatenated in order) forms a \(k\)-super-real numeral string.

The grammar for a fixed \(k\) may be summarized as follows:

Let \(S\) be a \(k\)-super-real numeral string. Then

[ S ;::=; \epsilon ;|; S,S ;|; {,S,\underbrace{|,S,|,\cdots,|,S}_{k \text{ times}}}\ . ]

Note that for \(k=0\) the production \(\{ S \}\) is allowed while for \(k \ge 1\) the block must contain exactly \(k\) copies of | separating \(k+1\) substrings.

Your task is to compute \(m+1\) numbers: the count of ordered pairs \((x,y)\) whose path string is a \(k\)-super-real numeral string for each \(k = 0, 1, \ldots, m\).

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of nodes and the maximum \(k\) to consider).

The second line contains \(n\) characters separated by spaces, each being one of {, |, or } representing \(a_1, a_2, \ldots, a_n\).

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) (an edge between nodes \(u\) and \(v\)).

It is guaranteed that the given graph is a tree.

outputFormat

Output a single line containing \(m+1\) space‐separated integers. The \(i\)th number (starting from \(i=0\)) represents the number of ordered pairs \((x,y)\) such that the string formed by the characters along the unique simple path from \(x\) to \(y\) is a \(i\)-super-real numeral string.

sample

1 1
{

0 0