传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3756

题解：乱搞

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define ll long long 7 #define maxn 1600005  8 using namespace std; 9 int val[maxn],fa[maxn],son[maxn][3],ri[maxn],tmp[maxn],fin[maxn];10 int d[maxn],tail=0,head=0,qq[maxn];11 12 ll sum[maxn],ans;13 char s[maxn*10];14 int n,m,tot,root,last;15     int newnode(int x){val[++tot]=x; return tot;}16     void extend(int x)17     {18         int p=last,np=newnode(val[p]+1); ri[np]=1;19         for (; p && !son[p][x]; p=fa[p]) son[p][x]=np;20         if (!p) fa[np]=root;21         else22         {23             int q=son[p][x];24             if (val[p]+1==val[q]) fa[np]=q;25             else26             {27                 int nq=newnode(val[p]+1);28                 memcpy(son[nq],son[q],sizeof(son[q]));29                 fa[nq]=fa[q]; fa[q]=fa[np]=nq;30                 for (; p&& son[p][x]==q; p=fa[p]) son[p][x]=nq;31             }32         }33         last=np;34     }35     void Tsort()36     {37         memset(d,0,sizeof(d));38         for(int i=1;i<=tot;i++) d[fa[i]]++;39         for(int i=1;i<=tot;i++) if(d[i]==0) qq[++tail]=i;40         while(head
           
            =1; i--) tmp[sum[val[i]]--]=i;49 memset(sum,0,sizeof(sum));50 ri[root]=val[root]=val[0]=0;51 for (int i=1; i<=tot; i++)52 {53 int x=tmp[i];54 sum[x]=1ll*ri[x]*(val[x]-val[fa[x]]);55 if (fa[x]) sum[x]+=sum[fa[x]];56 }57 sum[root]=0;58 }59 void work()60 {61 int len=0;62 scanf("%s",s+1); m=strlen(s+1); last=root;63 for (int i=1; i<=m; i++) 64 {65 int x=s[i]-'a';66 if (son[last][x]) last=son[last][x],len++;67 else68 {69 for (; last && !son[last][x]; last=fa[last]) ;70 if (last) len=val[last]+1,last=son[last][x];71 else len=0,last=root;72 }73 if (last!=root&&last){74 ans+=(sum[fa[last]]+1ll*(len-val[fa[last]])*ri[last]);75 }76 }77 printf("%lld\n",ans);78 }79 int main()80 {81 scanf("%d\n",&n); char ch[3]; 82 tot=root=last=fin[1]=1;83 for (int i=2; i<=n; i++)84 {85 int k;86 scanf("%d%s",&k,ch+1); last=fin[k]; extend(ch[1]-'a'); fin[i]=last;87 }88 Tsort();89 work();90 }
           
          
         
        
       
      

Fuck ls 看了ls错误建图，懒得改了。。。。

开始时间：+

结束时间：-