E. Модны тэмдэгт мөрийн бодлого

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Үндэстэй мод нь үндэс гэж нэрлэгдэх онцгой оройтой, ямар ч циклгүй холбогдсон, чиглэлгүй графыг хэлнэ. $n$ оройтой үндэстэй модыг авч үзье, энд оройнууд нь 1-с $n$ хүртэл дугаарлагдах ба энэ бодлогод 1 дугаартай орой нь үргэлж модны үндэс байна.

Модон дахь $v$ ба $u$ оройнуудын хоорондох хамгийн богино замын уртыг уг замын ирмэгүүдийн тоогоор буюу $d(v, u)$ гэж тэмдэглэе.

$r$ $(v ≠ r)$ орой дээр үндэстэй модны $v$ оройн эцэг орой нь $p_{v}$ байх ба $d(r, p_{v}) + 1 = d(r, v)$ болон $d(p_{v}, v) = 1$ байна. Жишээлбэл зураг дээрх $v = 5$ оройн эцэг орой нь $p_{5} = 2$ байна.

Нэг өдөр Поликарпус $n$ оройтой үндэстэй модтой таарсан. Уг мод маань яг ч энгийн мод байсангүй: модны ирмэгүүд дээр тэмдэгт мөр бичсэн байв. Поликарпус модыг талбар дээр хэрвээ та эцэг оройгоос нь уг оройруу явбал бүх ирмэг нь дээрээс доош чиглэсэн байхаар байрлуулав (зургийг харна уу). $p_{v}$ оройгоос $v$ $(1 < v ≤ n)$ оройруу чиглэсэн дурын ирмэгийн хувьд Поликарпус түүн дээр бичигдсэн $s_{v}$ тэмдэгт мөрийг мэдэж байна. Бүх тэмдэгт мөрүүд ирмэгүүд дээр дээрээс доош чиглэлтэй бичигдсэн байна. Жишээлбэл зураг дээр $s_{7}$="$ba$" байна. Тэмдэгт мөрийн тэмдэгтүүд 0-ээс эхлэн дугаарлагдана.

Поликарпусын модны жишээ (бодлогын нөхцөл дээрх жишээтэй харгалзана).

Поликарпус энэ модон дээрх байрлалыг тодорхой тэмдэгт мөрийн тодорхой үсэг хэлбэрээр тодорхойлсон. Байрлал нь $(v, x)$ хос тоогоор илэрхийлэгдэх ба энэ нь $s_{v}$ ($1 < v ≤ n$, $0 ≤ x < |s_{v}|$) тэмдэгт мөрийн $x$-р үсэг гэсэн үг ба энд $|s_{v}|$ нь $s_{v}$ тэмдэгт мөрийн урт байна. Жишээлбэл тодруулсан үсэгнүүд нь ($2, 1$) ба ($3, 1$) байрлалууд дээр байна.

Поликарпусийн модон дахь $(v, x)$ ба $(u, y)$ байрлалуудыг авч үзье. Поликарпусын мод нь алхам бүрт эхний байрлалаас хоёр дахь байрлалруу доош явахаар байна. Бид ийм хоёр байрлал нь $z$ тэмдэгт мөрийг тодорхойлно гэж үзнэ. $z$ тэмдэгт мөр нь $(v, x)$-с $(u, y)$ хүрэх зам дээр бичигдсэн бүх тэмдэгтийг агуулна. Жишээлбэл зураг дээр тодруулсан байрлалууд маань "$bacaba$" тэмдэгт мөрийг тодорхойлж байна.

Поликарпуст $t$ тэмдэгт мөр байгаа ба уг $t$ тэмдэгт мөрийг тодорхойлох хос байрлалуудын тоог мэдэхийг хүсч байна. Эхний байрлалаас хоёр дахь байрлалруу явах зам нь үргэлж доошоо чиглэлтэй байх ёстой. Түүнд уг модны-тэмдэгт мөрийн бодлогыг шийдэхэд туслана уу.

Оролт

Эхний мөрөнд бүхэл тоо $n$ $(2 ≤ n ≤ 10^{5})$ байх буюу Поликарпусийн модны оройнуудын тоо юм. Дараагийн $n - 1$ мөрөнд модны ирмэгүүдийг агуулна. $i$-р мөрөнд $p_{i + 1}$ тоо ба $s_{i + 1}$ $(1 ≤ p_{i + 1} ≤ n; p_{i + 1} ≠ (i + 1))$ тэмдэгт мөр байна. $s_{i + 1}$ тэмдэгт мөр нь хоосон биш ба Англи цагаан толгойн жижиг үсгүүдээс бүрдэнэ. Сүүлийн мөрөнд $t$ тэмдэгт мөр байна. $t$ тэмдэгт мөр нь Англи цагаан толгойн жижиг үсгээс бүрдэх ба хамгийн багадаа 2 урттай байна.

Оролтонд хамгийн ихдээ $3*10^{5}$ Англи үсэг байна.

Гаралт

Шаардлагатай тоог илэрхийлэх нэг бүхэл тоог хэвлэ.

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
aba
Гаралт
6
Оролт
7
1 ab
5 bacaba
1 abacaba
2 aca
5 ba
2 ba
bacaba
Гаралт
4

Тэмдэглэл

Эхний жишээн дээр "$aba$" тэмдэгт мөрийг дараах хос байрлалууд тодорхойлж чадна: (2, 0) ба (5, 0); (5, 2) ба (6, 1); (5, 2) ба (3, 1); (4, 0) ба (4, 2); (4, 4) ба (4, 6); (3, 3) ба (3, 5).

Тэмдэгт мөрийг маань (7, 1) ба (5, 0) байрлалууд тодорхойлж чадахгүй ба учир нь тэдгээрийн хоорондох зам үргэлж доош чиглэсэн байж чадахгүй байна.

Сэтгэгдлүүдийг ачааллаж байна...