시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB89217011421.965%

문제

만영이는 산책을 좋아한다. 만영이가 사는 마을에는 정원이 있는데, 정원에는 N개의 쉼터가 있고, 1번 쉼터에는 정원의 입구가 있다.

정원에는 26종류의 꽃이 있고 만영이는 각 꽃에 a부터 z까지의 서로 다른 알파벳 소문자로 이름을 지어주었다. 정원의 쉼터는 N-1개의 길로 연결되어 있다. 하나의 길은 이 중 한 종류의 꽃으로만 장식되어있다.

정원은 길을 따라 쉼터에서 다른 쉼터로 이동하는 구조이지만, 길이 너무 좁아서 산책하는 사람들이 다칠 수 있기 때문에 정해진 방향이 아닌 반대 방향으로 이동하는 것은 금지되어있다. 물론, 정원은 입구에서 출발한다면 어떤 쉼터로든 갈 수 있도록 설계되어있다.

<그림1> 정원의 한 예 (예제 1)

만영이는 수많은 산책 끝에 특별한 순서대로 꽃을 보게 되면 기분이 좋아진다는 사실을 깨달았다. 만영이는 만영이의 취향에 완벽하게 부합해, 산책하면 기분이 좋아지는 산책로를 '만영로'라고 부르기로 했다.

예를 들어, 만영이의 취향이 "ab" 라면 <그림1>에는 [1, 2, 3], [3, 4, 5], [4, 7, 8], [4, 7, 9] 총 4개의 만영로가 있다. 만영이의 취향이 "aab" 라면 [3, 4, 7, 9], [3, 4, 7, 8] 총 2개의 만영로가 있다. [7, 4, 3]는 정해진 방향이 아닌 반대 방향으로 걷는 산책로이므로, 만영로가 될 수 없다.

만영이는 정원 안에 만영로가 총 몇 개나 있는지 알고 싶다.

입력

첫 줄에는 정원 내 쉼터의 개수 N이 주어진다.

두 번째 줄부터 N-1 줄에 걸쳐 쉼터를 잇는 길의 정보 u, v, c가 주어진다. 이는 u번에서 v번 쉼터로 갈 수 있는 길이 이름이 c인 꽃으로 장식되어 있음을 의미한다.

다음 줄에 만영이의 취향을 나타내는 문자열 P가 주어진다.

출력

정원 안 만영로의 개수를 출력한다.

서브태스크 1 (100점)

  • 1 ≤ N ≤ 10,000
  • 1 ≤ |P| ≤ 1,000

서브태스크 2 (40점)

  • 1 ≤ N ≤ 500,000
  • 1 ≤ |P| ≤ 500,000

예제 입력 1

10
1 2 a
2 3 b
3 4 a
4 5 b
5 6 a
4 7 a
7 8 b
7 9 b
9 10 a
ab

예제 출력 1

4

채점 및 기타 정보

  • 예제는 채점하지 않는다.