解法
SAM:
首先用trie树建sam,和一般的sam不同的地方在于转移的位置不再是直接用ed,而是根据该节点在trie树上的祖先。
然后就是跑LCP操作,统计答案。统计答案时需要计算每个节点所代表的字符串数量val[i]和从根节点到每个节点的val的前缀和sum,然后就可以了,注意统计前缀和的时候需要另一次dfs
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
#define int long long
inline int read(){
char c=getchar();int t=0,f=1;
while((!isdigit(c))&&(c!=EOF)){if(c=='-')f=-1;c=getchar();}
while((isdigit(c))&&(c!=EOF)){t=(t<<3)+(t<<1)+(c^48);c=getchar();}
return t*f;
}
int n;
int fa[maxn],ch[maxn][3],sz[maxn],ct=1,len[maxn],ed=1,id[maxn];
long long val[maxn],sum[maxn];
inline int insert(int c,int lst){
int np=++ct,p=lst;len[np]=len[ed]+1;sz[np]=1;ed=ct;
for(;p&&(!ch[p][c]);p=fa[p])ch[p][c]=np;
if(!p){fa[np]=1;}
else{
int q=ch[p][c];
if(len[q]==len[p]+1){
fa[np]=q;
}
else{
int nq=++ct;len[nq]=len[p]+1;
for(int i=0;i<3;i++)ch[nq][i]=ch[q][i];
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;p&&(ch[p][c]==q);p=fa[p])ch[p][c]=nq;
}
}
return np;
}
vector<int> g[maxn];
void dfs(int u){
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
dfs(v);
sz[u]+=sz[v];
}
//printf("%d %d\n",sz[u],len[u]-len[fa[u]]);
val[u]=1ll*sz[u]*(len[u]-len[fa[u]]);
}
void dfs2(int u){
sum[u]=val[u]+sum[fa[u]];
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
dfs2(v);
}
}
char s[8000005];
signed main(){
n=read();id[1]=1;
for(int i=2;i<=n;i++){
int fa=read();
char c;scanf("%c",&c);
id[i]=insert(c-'a',id[fa]);
}
for(int i=2;i<=ct;i++)g[fa[i]].push_back(i);
dfs(1);
scanf("%s",s+1);
int l=strlen(s+1),p=1,lenth=0;
long long ans=0;
dfs2(1);
// for(int i=1;i<=ct;i++)
//printf("%d %d %d\n",len[i],fa[i],sum[i]);
for(int i=1;i<=l;i++){
int c=s[i]-'a';
if(ch[p][c]){
p=ch[p][c];lenth++;
}
else{
while(p&&!ch[p][c])p=fa[p];
if(!p){p=1;lenth=0;}
else{
lenth=len[p]+1;p=ch[p][c];
}
}
ans=ans+sum[fa[p]]+1ll*(lenth-len[fa[p]])*sz[p];
}
printf("%lld\n",ans);
return 0;
}