Word Counting

Time limit1sMemory limit128 MB

Summary

Given a rooted tree whose edges carry letter strings, count distinct occurrences of a query word along all paths from the root to the leaves, identifying each occurrence by its start and end position.

Level: Hard8 of 10
Topics: String matching, Trie, DFS, Tree
Solved: No attempts yet

Problem

On a distant island, Thales invented a game: he would pick a word and count how many times it appeared in the text written along the roads. To make it harder, he drew a map of every path leading from his current position to the ports from which he could sail home.

The roads form a tree. Different paths may share a common beginning, but once two paths separate they never meet again, and every path ends at a different port. Node $0$ is the origin (where the word is chosen); the remaining nodes are road splits or ports (the leaves). Each road segment is labeled with a text made of lowercase English letters.

Your task is to count all distinct appearances of a chosen word along the paths from the origin to the ports.

Input

The first line contains an integer $N$ ( $2 \le N \le 15000$ ), the number of nodes.

Each of the next $N - 1$ lines describes one road: two integers $I$ and $J$ ( $0 \le I, J \le N - 1$ ) followed by a text $S$ of length $L$ ( $1 \le L \le 1000$ ). This is a road from node $I$ to node $J$ labeled with $S$ , where $I$ is the parent of $J$ . There is no road into node $0$ , and no road starts from a port.

The last line contains the word to count. Every letter that appears is a lowercase English letter.

Output

Print a single integer: the number of distinct appearances of the word along all paths from the origin to the ports.

Hint

An appearance is identified by its start position and its end position, where the end position follows the start position along a path. An appearance exists exactly when the letters read consecutively from the start position to the end position (inclusive) spell the word. Two appearances are different if they differ in start position or in end position.

Because paths share a common beginning but branch apart, an appearance that lies entirely on a shared part is counted once, whereas appearances that coincide before a branch but end on different branches are counted separately.

In the example input, the word honey appears four times, along these parts of the paths: (0-7-6), (0-7-8), (0-7-2-5), and (2-4).

Example tree

Examples3

Example 1

Input

11
0 7 who
7 8 neyz
7 1 me
7 2 ne
2 3 ver
2 4 sthoneyz
2 5 y
7 6 ney
6 9 yenoh
6 10 xyz
honey

Expected output

Example 2
Input
```
4
0 1 ab
1 2 c
1 3 c
abc
```
Expected output
```
2
```
Example 3
Input
```
4
0 1 abc
1 2 x
1 3 y
abc
```
Expected output
```
1
```