您有一棵以节点 $$$1$$$ 为根、有 $$$n$$$ 节点的树。每个节点上都写有一个小写英文字母。
对于从$$$1$$$到$$$n$$$的每个整数$$$i$$$,请独立解决以下问题:
- 考虑由以下过程形成的字符串集:
- 选择 $$$i$$$ 子树中的任意节点 $$$u$$$ 作为起始位置。
- 重复 0 次或多次:
- 假设您当前位于节点 $$$x$$$ 上。选择节点$$$x$$$的子树$$$^{\text{∗}}$$$中的节点$$$v$$$,但您可以 不 选择$$$v=x$$$。移动到节点$$$v$$$。该过程可以随时终止。
- 从您经过的所有节点(按顺序)获取的字符连接起来形成一个字符串。
您对每个可能的路径都执行了一次上述过程。如果一个节点在一条路径中被访问但在另一条路径中未被访问,则认为两条路径是不同的。
现在,您已经获得了很多字符串。您想知道每种类型的字符串出现次数的平方和。由于这个答案可能非常大,因此输出其对 $$$998\,244\,353$$$ 取模的值。
$$$^{\text{*}}$$$当且仅当从节点 $$$1$$$ 到节点 $$$v$$$ 的最短路径经过节点 $$$x$$$ 时,节点 $$$v$$$ 位于另一个节点 $$$x$$$ 的子树中。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$)。
下一行是一个长度为 $$$n$$$ 的字符串,仅包含小写英文字母,其中第 $$$i$$$ 个字符表示第 $$$i$$$ 个节点上的字母。
接下来是 $$$n-1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n, u \neq v$$$) 表示树的一条边。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,在新行中输出 $$$n$$$ 数字:$$$i=1,2,\ldots,n$$$ 的答案,模 $$$998\,244\,353$$$。
示例
输入复制
53abb1 21 32aa1 24ccbb1 22 32 44aaaa1 44 22 310cacbcccbac1 22 33 42 51 62 73 84 98 10
输出复制
9 1 15 129 9 1 169 5 1 19185 65 19 3 1 1 1 3 1 1
注意
对于第一个测试用例:
- 对于节点 $$$2$$$ 和 $$$3$$$,可以从进程中获取的唯一字符串是 b。因此,两者的答案都是 $$$1$$$。
- 对于节点 $$$1$$$,可能的字符串是 a, ab, ab, b,和 b。总体而言, a 可以通过一种方式获得,而 ab 和 b 可通过两种方式获得。因此,节点$$$1$$$的答案是$$$1^2+2^2+2^2=9$$$。
在第四个测试用例中,对于节点 $$$1$$$,可能的字符串为:
- 啊啊啊 (可通过 $$$1$$$ 方式获得)
- aaa (可通过 $$$4$$$ 方式获得)
- aa (可通过 $$$6$$$ 方式获得)
- a (可通过 $$$4$$$ 方式获得)
因此,节点 $$$1$$$ 的答案是 $$$1^2+4^2+6^2+4^2=69$$$。