传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3756
题解：乱搞
代码：
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define ll long long
#define maxn 1600005
using namespace std;
int val[maxn],fa[maxn],son[maxn][],ri[maxn],tmp[maxn],fin[maxn];
int d[maxn],tail=,head=,qq[maxn]; ll sum[maxn],ans;
char s[maxn*];
int n,m,tot,root,last;
int newnode(int x){val[++tot]=x; return tot;}
void extend(int x)
{
int p=last,np=newnode(val[p]+); ri[np]=;
for (; p && !son[p][x]; p=fa[p]) son[p][x]=np;
if (!p) fa[np]=root;
else
{
int q=son[p][x];
if (val[p]+==val[q]) fa[np]=q;
else
{
int nq=newnode(val[p]+);
memcpy(son[nq],son[q],sizeof(son[q]));
fa[nq]=fa[q]; fa[q]=fa[np]=nq;
for (; p&& son[p][x]==q; p=fa[p]) son[p][x]=nq;
}
}
last=np;
}
void Tsort()
{
memset(d,,sizeof(d));
for(int i=;i<=tot;i++) d[fa[i]]++;
for(int i=;i<=tot;i++) if(d[i]==) qq[++tail]=i;
while(head<tail){
int x=qq[++head];
ri[fa[x]]+=ri[x];
if((--d[fa[x]])==) qq[++tail]=fa[x];
}
memset(sum,,sizeof(sum));
for (int i=; i<=tot; i++) sum[val[i]]++;
for (int i=; i<=tot; i++) sum[i]+=sum[i-];
for (int i=tot; i>=; i--) tmp[sum[val[i]]--]=i;
memset(sum,,sizeof(sum));
ri[root]=val[root]=val[]=;
for (int i=; i<=tot; i++)
{
int x=tmp[i];
sum[x]=1ll*ri[x]*(val[x]-val[fa[x]]);
if (fa[x]) sum[x]+=sum[fa[x]];
}
sum[root]=;
}
void work()
{
int len=;
scanf("%s",s+); m=strlen(s+); last=root;
for (int i=; i<=m; i++)
{
int x=s[i]-'a';
if (son[last][x]) last=son[last][x],len++;
else
{
for (; last && !son[last][x]; last=fa[last]) ;
if (last) len=val[last]+,last=son[last][x];
else len=,last=root;
}
if (last!=root&&last){
ans+=(sum[fa[last]]+1ll*(len-val[fa[last]])*ri[last]);
}
}
printf("%lld\n",ans);
}
int main()
{
scanf("%d\n",&n); char ch[];
tot=root=last=fin[]=;
for (int i=; i<=n; i++)
{
int k;
scanf("%d%s",&k,ch+); last=fin[k]; extend(ch[]-'a'); fin[i]=last;
}
Tsort();
work();
}
Fuck ls 看了ls错误建图，懒得改了。。。。
开始时间：+
结束时间：-