트리의 팰린드롬

n개의 정점으로 이루어진 트리(연결된 비순환 무방향 그래프)가 주어진다. 정점에는 1부터 n까지 번호가 매겨져 있으며, 각 정점에는 a부터 t까지의 문자 중 하나가 할당되어 있다.

경로에 있는 레이블을 순열한 것 중 적어도 하나가 팰린드롬이면, 트리의 그 경로를 팰린드롬 경로라고 한다.

각 정점에 대해, 그 정점을 지나는 팰린드롬 경로의 수를 출력한다.

참고: 정점 u에서 정점 v로 가는 경로는 정점 v에서 정점 u로 가는 경로와 같은 것으로 간주하며, 이 경로가 지나는 각 정점에 대해 이 경로는 한 번만 센다.

첫째 줄에 트리의 정점 수를 나타내는 정수 n (2 ≤ n ≤ 2·105)가 주어진다.

다음 n - 1개의 각 줄에는 정점 u와 정점 v를 연결하는 간선을 나타내는 두 정수 u와 v (1 ≤ u, v ≤ n, u ≠ v)가 주어진다. 주어진 그래프가 트리임이 보장된다.

다음 줄에는 a부터 t까지의 소문자 n개로 이루어진 문자열이 주어지며, i-th (1 ≤ i ≤ n) 문자는 트리에서 정점 i의 레이블이다.

한 줄에 n개의 정수를 출력한다. 그중 i-th 정수는 트리에서 정점 i을 지나는 팰린드롬 경로의 수이다.

첫 번째 예제에서 다음 경로들은 팰린드롬 경로이다.

2 - 3 - 4

2 - 3 - 5

4 - 3 - 5

또한 정점을 하나만 포함하는 모든 경로는 팰린드롬 경로이다. 아래에는 첫 번째 예제에서 팰린드롬 경로가 아닌 몇 가지 경로를 나열했다.

1 - 2 - 3

1 - 2 - 3 - 4

1 - 2 - 3 - 5