这题就比较有趣了。

首先匹配一遍，然后统计子树叶子节点中包含大于等于k的节点个数（HH的项链）

然后就可以搞了。

关于合法的情况数，显然是l[i]-l[fa[i]]，然后向下下传即可（YY一下）。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define maxn 600005struct Query{    int l,r,id;    void print(){printf("Query : %d to %d (id is %d)\n",l,r,id);}}brr[maxn];bool cmp(Query a,Query b){return a.l==b.l?a.r
          
           

v[maxn],vb[maxn]; int h[maxn],to[maxn],ne[maxn],en,in[maxn],out[maxn]; int go[maxn][26],l[maxn],fa[maxn]; void init() { last=cnt=1; en=0; memset(h,-1,sizeof h); memset(go,0,sizeof go); } void add(int x,int id) { int p=last,q; if (q=go[p][x]) { if (l[q]==l[p]+1) last=q; else { int nq=++cnt; l[nq]=l[p]+1; memcpy(go[nq],go[q],sizeof go[q]); fa[nq]=fa[q]; fa[q]=nq; for(;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq; last=nq; } } else { int np=++cnt; l[np]=l[p]+1; for (;p&&!go[p][x];p=fa[p]) go[p][x]=np; if (!p) fa[np]=1; else { q=go[p][x]; if (l[q]==l[p]+1) fa[np]=q; else { int nq=++cnt; l[nq]=l[p]+1; memcpy(go[nq],go[q],sizeof go[q]); fa[nq]=fa[q]; fa[q]=fa[np]=nq; for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq; } } last=np; } v[last].push_back(id); vb[id].push_back(last); } void addedge(int a,int b) { to[en]=b; ne[en]=h[a]; h[a]=en++; } void ins(int id) { last=1;scanf("%s",s+1); int len=strlen(s+1); F(j,1,len) add(s[j]-'a',id); } void dfs(int o) { in[o]=++tot; for (int i=0;i

=0;i=ne[i]) dfs(to[i]); out[o]=tot; ++top;brr[top].l=in[o];brr[top].r=out[o];brr[top].id=o; } void dfs2(int o) { for (int i=h[o];i>=0;i=ne[i]) f[to[i]]+=f[o],dfs2(to[i]); } int lst[maxn],nxt[maxn],ans[maxn],f[maxn]; void solve() { init(); scanf("%d%d",&n,&k); F(i,1,n) ins(i); F(i,1,cnt) addedge(fa[i],i); dfs(1);// printf("Arr : ");F(i,1,tot) printf("%d ",arr[i]); printf("\n"); sort(brr+1,brr+top+1,cmp);// F(i,1,top) brr[i].print(); F(i,1,tot) { if (!lst[arr[i]]&&arr[i]) BT.add(i,1,tot); else nxt[lst[arr[i]]]=i; lst[arr[i]]=i; }// F(i,1,tot) printf("%d ",nxt[i]); printf("\n"); int now=1; F(i,1,top) { while (now

=k) f[i]=l[i]-l[fa[i]]; else f[i]=0; dfs2(1); F(i,1,n) { ll ans=0; F(j,0,vb[i].size()-1) ans+=f[vb[i][j]]; printf("%lld",ans); if (i!=n) printf(" "); } }}sam; int main(){sam.solve();}