CFCF2183F.Jumping Man

你有一棵根植于节点 $1$ 的树，树上有 $n$ 个节点。每个节点上都写有一个小写英文字母。

对于从 $1$ 到 $n$ 的每个整数 $i$，请分别解决下面的问题：

• 考虑由以下过程形成的字符串集合：

  • 选择位于 $i$ 子树中的任意节点 $u$ 作为起始位置。
  • 重复 0 次或更多次：
    • 假设你当前位于节点 $x$ 上，则你可以选择位于节点 $x$ 的子树 $^{\text{∗}}$ 中的节点 $v$，要求 $(v \ne 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$ 。

• 对于第一个测试案例：

  • 对于节点 $2$ 和 $3$，唯一可能从进程中获取的字符串是 b，因此，这两个节点的答案都是 $1$。
  • 对于节点 $1$，可能的字符串有 a、ab、ab、b 和 b。即，a 可以通过一种方式获得，而 ab 和 b 可以通过两种方式获得。因此，节点 $1$ 的答案是 $1^2+2^2+2^2=9$。

• 在第四个测试案例中，对于节点 $1$，可能的字符串有：

  • aaaa（可通过 $1$ 种方式得到）
  • aaa（有 $4$ 种方式）
  • aa（有 $6$ 种方式）
  • a（有 $4$ 种方式）
  • 因此，节点 $1$ 的答案为 $1^2+4^2+6^2+4^2=69$。