E. Палиндромы в дереве
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево (связный ациклический граф) на n вершинах. Вершины пронумерованы от 1 до n и на каждой вершине записана буква английского алфавита от a до t.

Путь в дереве называется палиндромным, если из букв, записанных на нём, можно составить палиндром (буквы можно произвольным образом переставлять).

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

Учтите, что путь из вершины u в вершину v и путь из вершины v в вершину u считаются одинаковыми, такие пути должны учитываться ровно один раз.

Входные данные

В первой строке содержится целое число n (2 ≤ n ≤ 2·105) — количество вершин в дереве.

В следующий n - 1 строках содержатся пары чисел u и v (1  ≤  u, v  ≤  n, u ≠ v), обозначающие ребро между вершинами u и v. Гарантируется, что заданный граф является деревом.

В следующей строке содержится строка, состоящая из n символов английского алфавита от a до t, где i-й (1 ≤ i ≤ n) символ обозначает букву, записанную в i-й вершине дерева.

Выходные данные

Выведите n чисел, где i-е число обозначает количество палиндромных путей, проходящих через вершину i.

Примеры
Входные данные
5
1 2
2 3
3 4
3 5
abcbb
Выходные данные
1 3 4 3 3
Входные данные
7
6 2
4 3
3 7
5 2
7 2
1 4
afefdfs
Выходные данные
1 4 1 1 2 4 2
Примечание

В первом тестовом примере следующие пути являются палиндромными:

2 - 3 - 4

2 - 3 - 5

4 - 3 - 5

Кроме того, все пути, состоящие из одной вершины, являются палиндромными. А следующие пути палиндромными не являются:

1 - 2 - 3

1 - 2 - 3 - 4

1 - 2 - 3 - 5