CF2183F.Jumping Man

You have a tree rooted at node $1$ with $n$ nodes. Each node has a lowercase English letter written on it.

For each integer $i$ from $1$ to $n$, please solve the following problem independently:

• Consider the set of strings formed by the following process:

  • Choose any node $u$ that is in the subtree of $i$ as your starting location.
  • Repeat 0 or more times:
    • Suppose you are currently on node $x$. Select a node $v$ that is in the subtree$^{\text{∗}}$ of node $x$, but you may not choose $v=x$. Move to node $v$. This process can be terminated at any point.
  • The characters obtained from all nodes you passed through (in order) are concatenated to form a string.

  You performed the above process exactly once for every possible path. Two paths are considered different if one node is visited in one path but not another.

  Now, you have obtained many strings. You want to know the sum of the square of the number of occurrences for each type of string. Since this answer might be very large, output its value modulo $998\,244\,353$.

$^{\text{∗}}$A node $v$ is in another node $x$'s subtree if and only if the shortest path from node $1$ to node $v$ passes through node $x$.

你有一棵以节点 $1$ 为根的树，共 $n$ 个节点。每个节点上写有一个小写英文字母。

对每个从 $1$ 到 $n$ 的整数 $i$，请独立求解以下问题：

• 考虑如下过程所生成的所有字符串构成的集合：

  • 任选一个位于节点 $i$ 的子树中的节点 $u$ 作为起始位置。
  • 重复执行 $0$ 次或多次以下操作：
    • 假设当前位于节点 $x$，选择一个节点 $v$，使得 $v$ 属于节点 $x$ 的子树$^{\text{∗}}$，但不允许取 $v = x$；然后移动到节点 $v$。该过程可在任意时刻终止。
  • 将所经过的所有节点上的字符（按访问顺序）拼接起来，形成一个字符串。

  对每一种可能的路径，上述过程恰好执行一次。若两条路径访问的节点序列不同（即存在某个节点在一条路径中被访问而在另一条中未被访问），则认为它们是不同的路径。

  此时，你得到了许多字符串。你需要计算：对每种不同的字符串，其出现次数的平方求和。由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

$^{\text{∗}}$ 节点 $v$ 属于节点 $x$ 的子树，当且仅当从节点 $1$ 到节点 $v$ 的最短路径经过节点 $x$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

For each test case, the first line contains an integer $n$ ($1 \le n \le 5000$).

The next line is a string of length $n$ containing only lowercase English letters, where the $i$-th character represents the letter on the $i$-th node.

This is followed by $n-1$ lines, each containing two integers $u$ and $v$ ($1 \leq u,v \leq n, u \neq v$) representing an edge of the tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output $n$ numbers on a new line: the answer for $i=1,2,\ldots,n$, modulo $998\,244\,353$.

对于每个测试用例，在新的一行输出 $n$ 个数：分别为 $i=1,2,\ldots,n$ 时的答案，对 $998\,244\,353$ 取模。

For the first test case:

• For nodes $2$ and $3$, the only string that is possible to get from the process is b. Therefore, the answer is $1$ for both.
• For node $1$, the possible strings are a, ab, ab, b, and b. Overall, a is obtainable in one way, while ab and b are obtainable in two ways. Therefore, the answer for node $1$ is $1^2+2^2+2^2=9$.

In the fourth test case, for node $1$, the possible strings are:

• aaaa (obtainable $1$ way)
• aaa (obtainable $4$ ways)
• aa (obtainable $6$ ways)
• a (obtainable $4$ ways)

Therefore, the answer for node $1$ is $1^2+4^2+6^2+4^2=69$.

对于第一个测试用例：

• 对于节点 $2$ 和 $3$，该过程唯一可能得到的字符串是 b。因此，两者的答案均为 $1$。
• 对于节点 $1$，可能得到的字符串为 a、ab、ab、b 和 b。总体而言，a 有 $1$ 种方式得到，而 ab 和 b 各有 $2$ 种方式得到。因此，节点 $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$。