这题好牛逼啊……

考虑对所有猫的名和姓建一个广义 SAM，然后处理两问。

求给出的串是多少只猫姓名的子串

先沿着 SAM 走，如果走不下去了答案就是 $0$，否则答案就是姓名串的每个前缀节点不断跳后缀连接可以到达当前点的个数。

把后缀树建出来，就是一个子树求和了，因为是静态的可以直接树上差分。

但是这样会算重，考虑经典套路，把每个点按照 dfs 序排序，然后差分的时候在相邻两个点的 lca 减掉一次贡献即可。

求每只猫的姓名中包含了多少个给出的串

几乎一样。

先在每个询问串的结束位置打标记，然后遍历整个后缀树，每到达一个姓名串的终点，就进行一次到根的链上求和即可。

还是会算重，还是在 lca 的位置减掉一次贡献即可。

时间复杂度 $O(n\log n)$。

#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
struct edge
{
    int nxt,to;
}e[100001<<2];
int n,m,tot,link[100001<<2],len[100001<<2],dfn[100001<<2],num,cnt,h[100001<<2],sum[100001<<2],val[100001<<2],fa[100001<<2][21],dep[100001<<2],res;
long long ans[100001<<2];
vector<pair<int,int> > v[100001<<2];
vector<int> str[100001<<2][2];
map<int,int> ch[100001<<2];
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x;
}
inline void add(int x,int y)
{
    e[++tot].nxt=h[x];
    h[x]=tot;
    e[tot].to=y;
}
inline void insert(int x,int tag)
{
    int node=0,l=read();
    for(int i=1;i<=l;++i)
    {
        int c=read();
        str[x][tag].emplace_back(c);
        if(!ch[node].count(c))
            ch[node][c]=++cnt;
        node=ch[node][c];
    }
}
inline int build(int lst,int c)
{
    int cur=ch[lst][c],p=link[lst];
    len[cur]=len[lst]+1;
    for(;~p;p=link[p])
        if(!ch[p].count(c))
            ch[p][c]=cur;
        else
            break;
    if(p==-1)
        return cur;
    int q=ch[p][c];
    if(len[p]+1==len[q])
    {
        link[cur]=q;
        return cur;
    }
    int clone=++cnt;
    link[clone]=link[q];
    len[clone]=len[p]+1;
    for(auto i:ch[q])
        if(len[i.second])
            ch[clone][i.first]=i.second;
    link[cur]=link[q]=clone;
    for(;~p;p=link[p])
        if(ch[p].count(c)&&ch[p][c]==q)
            ch[p][c]=clone;
        else
            break;
    return cur;
}
inline void bfs()
{
    link[0]=-1;
    queue<pair<int,int> > q;
    for(auto i:ch[0])
        q.push({0,i.first});
    while(!q.empty())
    {
        pair<int,int> k=q.front();
        q.pop();
        int node=build(k.first,k.second);
        for(auto i:ch[node])
            q.push({node,i.first});
    }
}
inline int LCA(int x,int y)
{
    if(dep[x]<dep[y])
        x^=y^=x^=y;
    for(int d=dep[x]-dep[y],i=0;1<<i<=d;++i)
        if(d&(1<<i))
            x=fa[x][i];
    if(x==y)
        return x;
    for(int i=20;~i;--i)
        if(fa[x][i]^fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    return fa[x][0];
}
inline void dfs1(int k,int f,int deep)
{
    dfn[k]=++num;
    dep[k]=deep;
    fa[k][0]=f;
    for(int i=1;i<=20;++i)
        fa[k][i]=fa[fa[k][i-1]][i-1];
    for(int i=h[k];i;i=e[i].nxt)
        dfs1(e[i].to,k,deep+1);
}
inline void dfs2(int k)
{
    for(int i=h[k];i;i=e[i].nxt)
    {
        dfs2(e[i].to);
        sum[k]+=sum[e[i].to];
    }
}
inline int query()
{
    bool flag=1;
    int node=0,l=read();
    for(int i=1;i<=l;++i)
    {
        int c=read();
        if(!flag)
            continue;
        if(!ch[node].count(c))
        {
            flag=0;
            continue;
        }
        node=ch[node][c];
    }
    if(!flag)
        return 0;
    ++val[node];
    return sum[node];
}
inline void dfs3(int k)
{
    res+=val[k];
    for(auto i:v[k])
        ans[i.first]+=i.second*res;
    for(int i=h[k];i;i=e[i].nxt)
        dfs3(e[i].to);
    res-=val[k];
}
inline bool cmp(int x,int y)
{
    return dfn[x]<dfn[y];
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
    {
        insert(i,0);
        insert(i,1);
    }
    /*for(int i=0;i<=cnt;++i)
        for(auto j:ch[i])
            cout<<i<<" "<<j.second<<" "<<j.first<<endl;
    cout<<endl;*/
    bfs();
    /*for(int i=0;i<=cnt;++i)
        for(auto j:ch[i])
            cout<<i<<" "<<j.second<<" "<<j.first<<endl;*/
    for(int i=1;i<=cnt;++i)
    {
        //cout<<link[i]<<" "<<i<<endl;
        add(link[i],i);
    }
    dfs1(0,-1,1);
    for(int i=1;i<=n;++i)
    {
        vector<int> tmp;
        int node=0;
        for(int j:str[i][0])
        {
            node=ch[node][j];
            tmp.emplace_back(node);
        }
        node=0;
        for(int j:str[i][1])
        {
            node=ch[node][j];
            tmp.emplace_back(node);
        }
        sort(tmp.begin(),tmp.end(),cmp);
        for(int j=0;j<(int)tmp.size();++j)
        {
            ++sum[tmp[j]];
            v[tmp[j]].push_back({i,1});
            if(j)
            {
                int lca=LCA(tmp[j-1],tmp[j]);
                --sum[lca];
                v[lca].push_back({i,-1});
            }
        }
    }
    dfs2(0);
    while(m--)
        printf("%d\n",query());
    dfs3(0);
    for(int i=1;i<=n;++i)
        printf("%lld ",ans[i]);
    puts("");
    return 0;
}