Alek 喜欢打信息竞赛, 尤其喜欢超现实树. 超现实树, 顾名思义, 就是树上的超现实数.
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 $-超现实数串.
输入格式
第一行两个整数 $ n, m $, 分别表示树的节点数, 和需要求答案的 $ k $ 的上限.
第二行一个字符串 $ a $, $ a $ 的第 $ i $ 个字符表示点 $ i $ 上的字符.
接下来 $ n - 1 $ 行, 每行两个整数 $ x, y $, 表示存在一条连接点 $ x $ 和点 $ y $ 的边.
输出格式
输出一行 $ m + 1 $ 个整数, 分别表示 $ k = 0, 1, \cdots, m $ 时的答案.
样例
样例 1 输入
5 3
|{}}}
2 1
3 2
4 1
5 1
样例 1 输出
1 2 0 0
样例 2 输入
10 8
|}||}{|{{{
2 1
3 1
4 3
5 2
6 5
7 5
8 4
9 2
10 3
样例 2 输出
2 0 1 1 0 0 0 0 0
样例 3
见附加文件 ex_surreal3.in/ans.
限制与约定
对于所有数据, 有 $ 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): 无特殊限制.
时间限制: 1s; 空间限制: 512MB.