Description：

给一个 $trie$ 树和一个字符串 $S$ ，求 $S$ 的所有子串和树上的所有路径的匹配总数。

$1\leqslant n\leqslant 800000$

Solution：

学到了建立 $trie$ 树上的广义后缀自动机的正确方式，就是为了防止重复加点，如果还没有转移就新建，否则不新建 $np$ ，有一些细节具体看代码，对 $right$ 集合和 $par$ 树的处理略有不同，然后统计答案就是设一个 $sum$ 表示这个位置所代表的最长的字符串和这个位置一直到根的所有其他子串的匹配总个数，转移为： $$ sum[k]=sum[s[k].par]+(s[k].maxl-s[s[k].par].maxl)\times |Right(k)| $$ 就是新出现的这些子串在 $Right$ 集合的每一个位置都会产生一个匹配，然后统计答案就是拿 $S$ 在上面匹配，如果匹配到这个位置就是说明匹配长度 $len$ 在 $[minl,maxl]$ 中，然后统计答案的式子和上面那个式子一样。

以后遇到所有子串的统计问题可以用这个方法，就是考虑在某个位置结束的所有子串，然后每个点预处理一个和所有祖先有关的量。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1600010

char s[MAXN * 6];

int pos[MAXN];

int rig[MAXN];

namespace SAM

{

	struct node

	{

		int tr[26];

		int par,maxl;

	}s[MAXN];

	int ptr = 1,root = 1;

	int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

	int extend(int last,int k)

	{

		int p = last;

		if(s[p].tr[k] != 0)

		{

			int q = s[p].tr[k];

			if(s[p].maxl + 1 == s[q].maxl)

			{

				++rig[q];

				return q;

			}

			else

			{

				int nq = newnode(s[p].maxl + 1);

				rig[nq] = 1;

				memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

				s[nq].par = s[q].par;

				s[q].par = nq;

				for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

				return nq;

			}

		}

		else

		{

			int np = newnode(s[p].maxl + 1);

			rig[np] = 1;

			for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

			if(p == 0)s[np].par = root;

			else

			{

				int q = s[p].tr[k];

				if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

				else

				{

					int nq = newnode(s[p].maxl + 1);

					memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

					s[nq].par = s[q].par;

					s[q].par = s[np].par = nq;

					for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

				}

			}

			return np;

		}

	}

	struct edge

	{

		int to,nxt,v;

	}e[MAXN];

	int edgenum = 0;

	int lin[MAXN] = {0};

	void add(int a,int b,int c)

	{

		e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

		return;

	}

	void dfs(int k,int cur)

	{

		pos[k] = cur;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			int nxt = extend(pos[k],e[i].v);

			dfs(e[i].to,nxt);

		}

		return;

	}

}

struct edge

{

	int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

void dfs1(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		dfs1(e[i].to);

		rig[k] += rig[e[i].to];

	}

	return;

}

typedef long long ll;

ll sum[MAXN];

void dfs2(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		int v = e[i].to;

		sum[v] = sum[k] + 1ll * (SAM::s[v].maxl - SAM::s[SAM::s[v].par].maxl) * rig[v];

		dfs2(e[i].to);

	}

	return;

}

int main()

{

	scanf("%d",&n);

	int fa;char c;

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

	{

		scanf("%d",&fa);

		c = getchar();

		while(!isalpha(c))c = getchar();

		SAM::add(fa,i,c - 'a');

	}

	SAM::dfs(1,1);

	for(int i = 2;i <= SAM::ptr;++i)add(SAM::s[i].par,i);

	dfs1(1);dfs2(1);

	scanf("%s",s + 1);

	int l = strlen(s + 1);

	int cur = SAM::root,len = 0;

	ll ans = 0;

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

	{

		if(SAM::s[cur].tr[s[i] - 'a'] != 0)

		{

			cur = SAM::s[cur].tr[s[i] - 'a'];

			++len;

		}

		else

		{

			while(cur != 1 && SAM::s[cur].tr[s[i] - 'a'] == 0)cur = SAM::s[cur].par;

			len = min(len,SAM::s[cur].maxl);

			if(SAM::s[cur].tr[s[i] - 'a'])

			{

				cur = SAM::s[cur].tr[s[i] - 'a'];

				++len;

			}

		}

		ans += sum[SAM::s[cur].par] + 1ll * (len - SAM::s[SAM::s[cur].par].maxl) * rig[cur];

	}

	cout << ans << endl;

	return 0;

}