← 返回题目列表

Codeforces · 2183/F

F. 跳跃人

中文机器翻译题面 查看原题

您有一棵以节点 $$$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$$$。

示例

输入
复制

5
3
abb
1 2
1 3
2
aa
1 2
4
ccbb
1 2
2 3
2 4
4
aaaa
1 4
4 2
2 3
10
cacbcccbac
1 2
2 3
3 4
2 5
1 6
2 7
3 8
4 9
8 10

输出
复制

9 1 1
5 1
29 9 1 1
69 5 1 19
185 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$$$。