#CW31. 树间跳步(jumpseq)

树间跳步(jumpseq)

题目描述

小 W 在一棵以结点 11 为根的树上跳跃。树有 nn 个结点,第 ii 个结点写有一个小写英文字母。

对一个指定结点 ii,小 W 可以在 ii 的子树中任选一个结点作为起点。当前位于结点 xx 时,他可以跳到 xx 的任意真后代,也可以立即停止。跳跃的两个结点不必由树边直接相连。把经过结点上的字符按访问顺序连接,得到一个非空字符串。

若两次跳跃过程访问的结点序列不同,则它们是不同跳跃序列,即使生成的字符串相同。

固定结点 ii 后,设字符串 ss 在上述跳跃序列中出现 ci,sc_{i,s} 次。对每个 i=1,2,…,ni=1,2,\dots,n,求所有出现过的字符串的

∑sci,s2\sum_s c_{i,s}^2

对 998244353998244353 取模后的结果。

输入格式

第一行输入一个整数 TT,表示测试数据组数。

每组数据中:

  1. 第一行输入一个整数 nn;
  2. 第二行输入一个长度为 nn 的小写字母串,第 ii 个字符属于结点 ii;
  3. 接下来 n−1n-1 行,每行输入两个整数 u,vu,v,表示树的一条边。

输出格式

对每组数据输出一行 nn 个整数,依次表示 i=1,2,…,ni=1,2,\dots,n 时的答案。每个整数均为对应答案对 998244353998244353 取模后的结果。

样例 1 输入

1
5
ababa
1 2
1 3
2 4
2 5

样例 1 输出

25 7 1 1 1

样例 1 解释

在样例 1 中,结点 22 的子树包含结点 2,4,52,4,5。生成 b 的单结点跳跃序列有两种;a、bb、ba 各有一种,因此结点 22 的答案为 22+12+12+12=72^2+1^2+1^2+1^2=7。

样例 2 输入

1
4
aaaa
1 2
2 3
3 4

样例 2 输出

69 19 5 1

样例 2 解释

样例 2 中可以越过中间结点。例如,从结点 11 直接跳到结点 33 是合法的。对结点 11,长度为 1,2,3,41,2,3,4 的全 a 跳跃序列分别有 4,6,4,14,6,4,1 种,所以答案为 42+62+42+12=694^2+6^2+4^2+1^2=69。

数据范围

对于所有测试数据:

  • 1≤T≤50001 \le T \le 5000;
  • 1≤n≤50001 \le n \le 5000;
  • 结点字符均为小写英文字母;
  • 输入边构成一棵树;
  • 所有测试数据的 ∑n≤5000\sum n \le 5000。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 n≤10n \le 10
B 15 3∼53\sim 5 n≤50n \le 50
C 20 6∼96\sim 9 n≤400n \le 400
D 25 10∼1410\sim 14 树是一条链,且结点 11 是链的一端
E 30 15∼2015\sim 20 无额外限制