#CW31. 树间跳步(jumpseq)
树间跳步(jumpseq)
题目描述
小 W 在一棵以结点 为根的树上跳跃。树有 个结点,第 个结点写有一个小写英文字母。
对一个指定结点 ,小 W 可以在 的子树中任选一个结点作为起点。当前位于结点 时,他可以跳到 的任意真后代,也可以立即停止。跳跃的两个结点不必由树边直接相连。把经过结点上的字符按访问顺序连接,得到一个非空字符串。
若两次跳跃过程访问的结点序列不同,则它们是不同跳跃序列,即使生成的字符串相同。
固定结点 后,设字符串 在上述跳跃序列中出现 次。对每个 ,求所有出现过的字符串的
对 取模后的结果。
输入格式
第一行输入一个整数 ,表示测试数据组数。
每组数据中:
- 第一行输入一个整数 ;
- 第二行输入一个长度为 的小写字母串,第 个字符属于结点 ;
- 接下来 行,每行输入两个整数 ,表示树的一条边。
输出格式
对每组数据输出一行 个整数,依次表示 时的答案。每个整数均为对应答案对 取模后的结果。
样例 1 输入
1
5
ababa
1 2
1 3
2 4
2 5
样例 1 输出
25 7 1 1 1
样例 1 解释
在样例 1 中,结点 的子树包含结点 。生成 b 的单结点跳跃序列有两种;a、bb、ba 各有一种,因此结点 的答案为 。
样例 2 输入
1
4
aaaa
1 2
2 3
3 4
样例 2 输出
69 19 5 1
样例 2 解释
样例 2 中可以越过中间结点。例如,从结点 直接跳到结点 是合法的。对结点 ,长度为 的全 a 跳跃序列分别有 种,所以答案为 。
数据范围
对于所有测试数据:
- ;
- ;
- 结点字符均为小写英文字母;
- 输入边构成一棵树;
- 所有测试数据的 。
| 数据类别 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| A | 10 | ||
| B | 15 | ||
| C | 20 | ||
| D | 25 | 树是一条链,且结点 是链的一端 | |
| E | 30 | 无额外限制 |