BOI’ 2005 RHODES Island – HELLAS 
3-8 September 2005
Bulgaria
Задача 3: Броене на думи

По време на лятната ваканция великите математици Талес и Архимед почивали на далечен остров, където интересните развлечения не били толкова много (очевидно,  не са били на остров Родос). Търсейки начини да се забавляват, Талес забелязал, че край пътищата са написани различни думи и фрази. Наистина, някои думи нямали смисъл, но това не му попречило да измисли следната игра.
Измисляш си някаква дума и броиш колко пъти се среща тази дума в текста по протежение на дадена отсечка от пътя (интервалите и пунктуационните знаци се игнорират). След известно време  това се сторило прекалено лесно на Талес и той решил да усложни задачата. Взел карта на острова и отбелязал всички пътища от техния град до пристанищата, откъдето могат да отпътуват с кораб за  вкъщи. Оказало се, че след като се разделят,  пътищата не се пресичат и всеки път завършва в различно пристанище. Новата задача е да се намери колко пъти се появява дадена дума по протежение на всичките пътища.  

Вход
Входните данни се четат от файл “wordcount.in”. 
Първият ред съдържа едно цяло число N (1≤N≤15000) – броят на пътните отсечки свързващи съседни градове. Следващите N-1 реда съдържат данни за отделните пътни отсечки. Градовете и пътищата между тях образуват дървовидна структура. Началото има номер 0. Останалите градове (някои от които са пристанища) са номерирани с числата от 1 до N‑1. Всеки от следващите N-1 реда от файла съдържа две цели числа I и J (0≤I,J≤N-1) и текст S с дължина L символа (1≤L≤1000), което означава, че по пътя от град I към град J (където I е винаги родител на J) е написан текста S. Разбира се, няма път към град 0 и от пристанищата не излизат пътища. Последният ред от входния файл съдържа думата,  за която трябва да се намери броя на срещанията. 

Изход
Програмата трябва да изведе във файла “wordcount.out” единствен ред, съдържащ едно цяло число – броя на срещанията на думата .

Забележка: Всяко появяване се определя от неговата начална и крайна точка, където крайната точка следва началната по протежение на пътя. Появяването е налице, когато конкатенацията на последователните букви от началната до крайната точка (включително) образува търсената дума. Две появявания са различни, когато се различават по начална или крайна точка. Всички участващи букви са малки букви от английската азбука.

Формат: Във всеки от файловете числата в един ред са разделени с единичен интервал. Всички редове завършват с край на ред.

Време за изпълнение: 2 секунди.

Пример (виж фигурата)
wordcount.in
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	wordcount.out
4	

Пояснение: Думата honey се среща четири пъти по следните пътища: (0-7-6), (0-7-8), (0-7-2-5) и (2-4).

3

10

0

7

8

1

2

6

9

5

4