#1798. 超现实树

    ID: 1798 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1422来源:qoj.ac数据:公开样例字符串

超现实树

超现实树

题目描述

标题: 超现实树 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

Alek 认为, 对于常数 k, 一个字符串被称为 "k-超现实数串", 如果其只包含字符 {',|',`}', 且:

  • 空串为 k-超现实数串;
  • 如果 s,t 为 k-超现实数串, 那么 s+t (加法表示字符串拼接) 为 k-超现实数串;
  • 如果 k+1 个字符串 s1,s2,⋯,sk+1 都是 k-超现实数串, 那么 {'+s1+|'+s2+|'+⋯+|'+sk+1+`}' 为 k-超现实数串;
  • k-超现实数串仅限于此.

给定一棵 n 个点的无根树, 节点编号为 1∼n. 每个点 i 上有一个字符 ai∈{{',|',`}'}.

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

输入格式

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

第二行一个字符串 a, a 的第 i 个字符表示点 i 上的字符.

接下来 n−1 行, 每行两个整数 x,y, 表示存在一条连接点 x 和点 y 的边.

输出格式

输出一行 m+1 个整数, 分别表示 k=0,1,⋯,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≤n≤105, 0≤m≤n−2, ai∈{{',|',`}'}.

  • Subtask 1 (5 分): n≤4601;
  • Subtask 2 (20 分): 对每条边 (x,y) 有 y=x+1;
  • Subtask 3 (5 分): ai≠`|', m=0;
  • Subtask 4 (15 分, 依赖 Subtask 3): m≤3;
  • Subtask 5 (25 分, 依赖 Subtask 1): n≤5×104;
  • Subtask 6 (30 分, 依赖 Subtask 1, 2, 3, 4, 5): 无特殊限制.

时间限制: 1s; 空间限制: 512MB.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 3
|{}}}
2 1
3 2
4 1
5 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 0 1 1 0 0 0 0 0