luogu#P10006. [集训队互测 2023] 超现实树

    ID: 13973 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>点分治WC/CTSC/集训队2023O2优化快速数论变换 NTT根号分治

[集训队互测 2023] 超现实树

题目背景

Alek 喜欢打信息竞赛,尤其喜欢超现实树。超现实树,顾名思义,就是树上的超现实数。

题目描述

Alek 认为,对于常数 kk,一个字符串被称为「kk-超现实数串」,如果其只包含字符 {,|,}\texttt{\{}, \texttt{|}, \texttt{\}},且:

  • 空串为 kk-超现实数串;
  • 如果 s,ts, tkk-超现实数串,那么 s+ts + tkk-超现实数串;
  • 如果 k+1k + 1 个字符串 s1,s2,,sk+1s_1, s_2, \cdots, s_{k + 1} 都是 kk-超现实数串,那么 $\texttt{\{} + s_1 + \texttt{|} + s_2 + \texttt{|} + \cdots + \texttt{|} + s_{k + 1} + \texttt{\}}$ 为 kk-超现实数串;
  • kk-超现实数串仅限于此。

给定一棵 nn 个点的无根树,节点编号为 1n1 \sim n。每个点 ii 上有一个字符 ai{{,|,}}a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}

给定整数 mm,Alek 希望你对 k=0,1,,mk = 0, 1, \cdots, m 分别求出:有多少有序对 (x,y)(x, y)1x,yn1 \leq x, y \leq n,使得树上从点 xx 到点 yy 的唯一简单路径上的字符依次拼接所得字符串是 kk-超现实数串。

输入格式

第一行两个整数 n,mn, m,分别表示树的节点数,和需要求答案的 kk 的上限。

第二行一个字符串 aaaa 的第 ii 个字符表示点 ii 上的字符。

接下来 n1n - 1 行,每行两个整数 x,yx, y,表示存在一条连接点 xx 和点 yy 的边。

输出格式

输出一行 m+1m + 1 个整数,分别表示 k=0,1,,mk = 0, 1, \cdots, m 时的答案。

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。

提示

对于所有数据,有 2n1052 \leq n \leq 10^50mn20 \leq m \leq n - 2ai{{,|,}}a_i \in \{\texttt{\{}, \texttt{|}, \texttt{\}}\}

  • Subtask 1(5 分):n4601n \leq 4601
  • Subtask 2(20 分):对每条边 (x,y)(x, y)y=x+1y = x + 1
  • Subtask 3(5 分):ai|a_i \neq \texttt{|}, m=0m = 0
  • Subtask 4(15 分,依赖 Subtask 3):m3m \leq 3
  • Subtask 5(25 分,依赖 Subtask 1):n5×104n \leq 5 \times 10^4
  • Subtask 6(30 分,依赖 Subtask 1, 2, 3, 4, 5):无特殊限制。