luogu#P10006. [集训队互测 2023] 超现实树
[集训队互测 2023] 超现实树
题目背景
Alek 喜欢打信息竞赛,尤其喜欢超现实树。超现实树,顾名思义,就是树上的超现实数。
题目描述
Alek 认为,对于常数 ,一个字符串被称为「-超现实数串」,如果其只包含字符 ,且:
- 空串为 -超现实数串;
- 如果 为 -超现实数串,那么 为 -超现实数串;
- 如果 个字符串 都是 -超现实数串,那么 $\texttt{\{} + s_1 + \texttt{|} + s_2 + \texttt{|} + \cdots + \texttt{|} + s_{k + 1} + \texttt{\}}$ 为 -超现实数串;
- -超现实数串仅限于此。
给定一棵 个点的无根树,节点编号为 。每个点 上有一个字符 。
给定整数 ,Alek 希望你对 分别求出:有多少有序对 ,,使得树上从点 到点 的唯一简单路径上的字符依次拼接所得字符串是 -超现实数串。
输入格式
第一行两个整数 ,分别表示树的节点数,和需要求答案的 的上限。
第二行一个字符串 , 的第 个字符表示点 上的字符。
接下来 行,每行两个整数 ,表示存在一条连接点 和点 的边。
输出格式
输出一行 个整数,分别表示 时的答案。
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。
提示
对于所有数据,有 ,,。
- Subtask 1(5 分):;
- Subtask 2(20 分):对每条边 有 ;
- Subtask 3(5 分):, ;
- Subtask 4(15 分,依赖 Subtask 3):;
- Subtask 5(25 分,依赖 Subtask 1):;
- Subtask 6(30 分,依赖 Subtask 1, 2, 3, 4, 5):无特殊限制。