题意：一棵树，每条边上有一些字符，求目标串出现了多少次

---

直接求目标串的fail然后一边dfs一边跑kmp

然后就被特殊数据卡到\(O(n^2)\)了...

因为这样kmp复杂度分析的基础就没有了，now指针可能每个孩子都减少n次

所以怒加trie图优化

貌似有人写了倍增+哈希的做法........

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;#define pii pair
          
           #define MP make_pair #define fir first#define sec secondconst int N=5e5+5, M=5e5+5;int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} return x*f;}int n, x, f[M], len, t[M][27]; char ch[M], str[M];struct edge{int v, ne; string s;}e[N];int cnt, h[N];inline void ins(int u, int v) { e[++cnt]=(edge){v, h[u], string(ch)}; h[u]=cnt;}int ans=0;void dfs(int u, int p) { for(int i=h[u];i;i=e[i].ne) { int now = p, v = e[i].v; string &s = e[i].s; for(int i=0; i<(int)s.size(); i++) { now = t[now][s[i]-'a']; if(now == len) ans++, now = f[now]; } dfs(v, now); }}int main() { //freopen("in","r",stdin); n=read(); for(int i=2; i<=n; i++) x=read(), scanf("%s",ch), ins(x, i); scanf("%s",str+1); len=strlen(str+1); f[1]=0; int now=0; for(int i=2; i<=len; i++) { now = f[i-1]; while(now && str[now+1] != str[i]) now = f[now]; f[i] = str[now+1] == str[i] ? now+1 : 0; } for(int i=0; i