Prelude

传送到Codeforces：(/ω＼)……… (/ω•＼)

---

Solution

很水的一道题。

对查询的串建出来AC自动机，然后树上随便跑跑就行了。

为什么要写这篇题解呢？

我第一眼看到这个题：“哈哈，有根树上的路径信息查询，点分治就好了，被我秒啦！”

“这个题好像是某Qualification Round的题啊。。。怎么Qual就出点分治啊，真毒瘤。”

然后码码码。。。

“怎么TLE了，卡卡常。”

卡常ing。。。

“怎么又WA了，难道卡哈希？毒瘤毒瘤。”

debugging。。。

“算了调不出来了拿tourist的代码拍一下吧。”

“这场比赛怎么AK了三百个人啊？这题怎么代码这么短啊？”

“。。。似乎KMP然后dfs一下就没了。。。我简直药丸。。。”

然后事实证明KMP的复杂度是错的，很容易就卡掉了，卡的方法也很简单，大家自己想想吧。。。

如果用KMP的话是TLE on test 30，如果是比赛就直接FST了。。。

所以用AC自动机就没问题了喵~

---

Code

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <queue>

using namespace std;

const int MAXN = 400010;

int _w;

int n, ch[MAXN], m;

char str[MAXN];

namespace G {

	int head[MAXN], nxt[MAXN], to[MAXN], eid;

	void init() {

		eid = 0;

		memset(head, -1, sizeof head);

	}

	void adde( int u, int v ) {

		to[eid] = v, nxt[eid] = head[u], head[u] = eid++;

	}

}

void add_edge( int u, int v, char *str ) {

	for( char *p = str; *p; ++p ) {

		ch[++m] = *p - 'a';

		if( p == str ) G::adde(u, m);

		else G::adde(m-1, m);

	}

	G::adde(m, v);

}

namespace AC {

	int ch[MAXN][26], nid;

	bool word[MAXN];

	queue<int> q;

	int f[MAXN];

	void insert( char *s ) {

		int u = 0;

		for( ; *s; ++s ) {

			int c = *s - 'a';

			if( !ch[u][c] )

				ch[u][c] = ++nid;

			u = ch[u][c];

		}

		word[u] = 1;

	}

	void build() {

		for( int i = 0; i < 26; ++i )

			if( ch[0][i] )

				q.push( ch[0][i] );

		while( !q.empty() ) {

			int u = q.front(); q.pop();

			for( int i = 0; i < 26; ++i ) {

				int v = ch[u][i];

				if( !v ) {

					ch[u][i] = ch[f[u]][i];

					continue;

				}

				int w = f[u];

				while( w && !ch[w][i] ) w = f[w];

				f[v] = ch[w][i];

				q.push(v);

			}

		}

	}

}

int ans;

void solve( int u, int o ) {

	using namespace G;

	if( ch[u] != -1 ) {

		o = AC::ch[o][ch[u]];

		if( AC::word[o] ) ++ans;

	}

	for( int i = head[u]; ~i; i = nxt[i] )

		solve( to[i], o );

}

int main() {

	_w = scanf( "%d", &n );

	m = n;

	G::init();

	for( int i = 2; i <= n; ++i ) {

		int pa;

		_w = scanf( "%d%s", &pa, str );

		add_edge(pa, i, str);

	}

	for( int i = 1; i <= n; ++i )

		ch[i] = -1;

	_w = scanf( "%s", str );

	AC::insert(str);

	AC::build();

	solve(1, 0);

	printf( "%d\n", ans );

	return 0;

}