F. Прыгающий человек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть дерево из $$$n$$$ вершин, корень которого находится в вершине $$$1$$$. На каждой вершине написана строчная латинская буква.

Для каждого целого числа $$$i$$$ от $$$1$$$ до $$$n$$$ решите следующую задачу независимо:

  • Рассмотрите множество строк, образованных следующим процессом:
    • Выберите любую вершину $$$u$$$, которая находится в поддереве вершины $$$i$$$, в качестве начальной точки.
    • Повторяйте 0 или более раз:
      • Предположим, что вы находитесь в вершине $$$x$$$. Выберите вершину $$$v$$$, которая находится в поддереве$$$^{\text{∗}}$$$ вершины $$$x$$$, но вы не можете выбрать $$$v=x$$$. Перейдите к вершине $$$v$$$. Этот процесс можно завершить в любой момент.
    • Символы, полученные от всех вершин, через которые вы прошли (по порядку), объединяются в строку.

    Вы выполнили вышеописанный процесс ровно один раз для каждого возможного пути. Два пути считаются различными, если одна вершина посещается в одном пути, но не в другом.

    Теперь вы получили множество строк. Вы хотите узнать сумму квадратов количества вхождений для каждого значения строки. Поскольку ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Вершина $$$v$$$ находится в поддереве другой вершины $$$x$$$, если и только если кратчайший путь от вершины $$$1$$$ до вершины $$$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$$$ возможны такие строки:

  • aaaa (есть $$$1$$$ способ получить)
  • aaa (есть $$$4$$$ способа получить)
  • aa (есть $$$6$$$ способов получить)
  • a (есть $$$4$$$ способа получить)

Поэтому ответ для вершины $$$1$$$ равняется $$$1^2+4^2+6^2+4^2=69$$$.