解题

题目所给的串的方式，相当于给出一个 Trie 树，每个人的名字是对应点到根的路径上的字符串。

考虑树上 SA，贺完板子后，每次查询就暴力在 $sa$ 数组上二分出两个边界。

具体地，完成一个比较函数，判定结点 $p$ 对应的字符串是否 $\ge$ 查询串，复杂度要求为 $O(\min(n,m))$，即为串长较小值。

第一次二分得到首个满足 $\ge$ 查询串的位置，第二次二分前，把查询串的最后一个字符加一，再次得到首个满足 $\ge$ 查询串的位置，两个位置构成一个左闭右开的区间。

实现

树上 SA 时间复杂度为 $O(n\log{n})$，二分时间复杂度为 $O(\sum_ilen_i\log{n})$，总时间复杂度 $O((n+\sum_ilen_i)\log{n})$。空间上，可以动态维护 $2^k$ 级祖先而不是用倍增数组储存，空间复杂度 $O(n)$。

:::info[code]

#include<bits/stdc++.h>
using namespace std;//判了 EOF
#define gc() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,IO,stdin))==rp1?EOF:*rp1++)
#define pc(a) ((wrp==obuf+IO&&(fwrite(obuf,1,IO,stdout),wrp=obuf)),(*wrp++)=a)

const int IO=1<<22,N=1000005;
char buf[IO+1],obuf[IO+1],*wrp=obuf;
char T[N],Q[N],*rp1,*rp2;
int n,q,m,sa[N],rk[N],id[N],cnt[N];
int fa[N],nxt[N],dep[N];

inline int read(){
    int a=0,c=gc();
    while(!isdigit(c)) c=gc();
    while(isdigit(c)) a=10*a+c-'0',c=gc();
    return a;
}

inline char read_char(){
    char c=gc();
    while(!isupper(c)) c=gc();
    return c;
}

inline void write(int x){
    int sk[20],top=0;
    do{
        sk[++top]=x%10,x/=10;
    }while(x);
    while(top) pc(sk[top--]+'0');
    pc('\n');
}

void init(){
    n=read(),q=read(),m=150;
    for(int i=1;i<=n;i++){
        T[i]=read_char(),nxt[i]=fa[i]=read();
        dep[i]=dep[fa[i]]+1;
    } 
    for(int i=1;i<=n;i++) cnt[rk[i]=T[i]]++;
    for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--) sa[cnt[rk[i]]--]=i;
}

void SA(){
    for(int t=1,now=0;t<n;t<<=1,m=now,now=0){
        memset(cnt,0,sizeof(int)*(m+2));
        for(int i=1;i<=n;i++) cnt[rk[fa[i]]]++;
        for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--) id[cnt[rk[fa[sa[i]]]]--]=sa[i];
        memset(cnt,0,sizeof(int)*(m+2));
        for(int i=1;i<=n;i++) cnt[rk[i]]++;
        for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--) sa[cnt[rk[id[i]]]--]=id[i];
        for(int i=1;i<=n;i++) id[i]=rk[i];
        rk[sa[1]]=now=1;
        for(int i=2;i<=n;i++){
            rk[sa[i]]=(id[sa[i]]==id[sa[i-1]]&&id[fa[sa[i]]]==id[fa[sa[i-1]]])?now:++now;
        }
        if(n==now) break;
        for(int i=n;i>=1;i--) fa[i]=fa[fa[i]];
    }
}

inline bool cmp(int p){//编号为 p 的结点的字典序是否 >= 当前查询串 
    for(int i=1;i<=m;p=nxt[p],i++){
        if(T[p]!=Q[i]) return T[p]>Q[i];
    }
    return 1;
}

int main(){
    init(),SA(),T[0]=0;//哨兵
    for(int i=1,L,R,mid,l0;i<=q;i++){
        char c=gc();m=0;
        while(!isupper(c)) c=gc();
        while(isupper(c)) Q[++m]=c,c=gc();
        for(L=1,R=n+1;L<R;){
            cmp(sa[mid=(L+R)>>1])?R=mid:L=mid+1;
        }
        for(l0=L,Q[m]++,R=n+1;L<R;){//可以不变动 L
            cmp(sa[mid=(L+R)>>1])?R=mid:L=mid+1;
        }
        write(L-l0);
    }
    return fwrite(obuf,1,wrp-obuf,stdout),0;
}

:::

#include <bits/stdc++.h>
using std::cin;
using std::cout;

const int N = 1000054;

namespace SAM {
	const int N = ::N * 2;

	int p, np, cnt = 1;
	int pa[N], val[N], d[N][26];
	int fc[N], nc[N], sum[N];

	#define q d[p][x]
	#define try_split(v) { \
		if (val[p] + 1 == val[q]) v = q; \
		else { \
			int nq = ++cnt; \
			val[nq] = val[p] + 1, memcpy(d[nq], d[q], 104); \
			pa[nq] = pa[q], v = pa[q] = nq; \
			for (int Q = q; p && q == Q; q = nq, p = pa[p]); \
		} \
	}

	int extend(int x) {
		if (p = np, q) try_split(np)
		else {
			for (val[np = ++cnt] = val[p] + 1; p && !q; q = np, p = pa[p]);
			if (p) try_split(pa[np]) else pa[np] = 1;
		}
		return sum[np] = 1, np;
	}
	#undef q

	inline void link(int x, int px) {nc[x] = fc[px], fc[px] = x;}

	void dfs(int x) {
		for (int y = fc[x]; y; y = nc[y]) dfs(y), sum[x] += sum[y];
	}

	inline void build() {
		for (int i = 2; i <= cnt; ++i) link(i, pa[i]);
		dfs(1);
	}
}

int n, q;
int d[N][26], que[N], sam[N];
char s[N];

void bfs(int si) {
	int i, x, y, h, t = 1;
	*que = si, sam[si] = 1;
	for (h = 0; h < t; ++h) {
		x = que[h];
		for (i = 0; i < 26; ++i) if ((y = d[x][i])) SAM::np = sam[x], sam[y] = SAM::extend(i), que[t++] = y;
	}
}

int main() {
	int i, x, t; char c;
	std::ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> n >> q;
	for (i = 2; i <= n + 1; ++i) cin >> c >> x, d[x + 1][c - 65] = i;
	bfs(1), SAM::build();
	for (; q; --q) {
		cin >> s, t = 1, x = strlen(s);
		for (i = x - 1; i >= 0 && t; --i) t = SAM::d[t][s[i] - 65];
		cout << SAM::sum[t] << '\n';
	}
	return 0;
}