本文共 3715 字，大约阅读时间需要 12 分钟。

这一题看了一下，首先反应SAM，肯定是最近SAM做的太多了。。
那么lcp自然就是倒串求LCA啊
嗯，感觉很对
接着再一看，数据有点大
好像不太好。。
那我们有虚树啊！
于是这题就成功地水过去了
感觉这题好题啊，把我最近学的东西都用上了，当然没有线性基。。
但这也说明我最近学得都很扎实，大概可能可以熟练运用了

#include<cstdio>#include<cstdlib>#include<algorithm>#include<iostream>#include<cstring>typedef long long LL;using namespace std;const int N=500005*2;struct qq{int son[26],step,pre;}s[N];int tot,Last;char ss[N];int n,m;void ins (int x){    int p=Last,np=++tot;    s[np].step=s[p].step+1;    while (p!=0&&s[p].son[x]==0) s[p].son[x]=np,p=s[p].pre;    if (p==0) s[np].pre=1;    else    {        int q=s[p].son[x];        if (s[p].step+1==s[q].step) s[np].pre=q;        else        {            int nq=++tot;            s[nq]=s[q];            s[nq].step=s[p].step+1;            s[q].pre=s[np].pre=nq;            while (p!=0&&s[p].son[x]==q) s[p].son[x]=nq,p=s[p].pre;        }    }    Last=np;}int pos[N];struct qr{int x,y,last;}e[N];int num,last[N];void init (int x,int y){    num++;    e[num].x=x;e[num].y=y;    e[num].last=last[x];    last[x]=num;}int lalal[N],cnt;int f[N][25],dep[N];int dfs (int x,int fa){    lalal[x]=++cnt;    dep[x]=dep[fa]+1;    f[x][0]=fa;    for (int u=1;(1<<u)<=dep[x];u++) f[x][u]=f[f[x][u-1]][u-1];    for (int u=last[x];u!=-1;u=e[u].last)    {        int y=e[u].y;        dfs(y,x);    }}int a[N];bool cmp (int x,int y){  return lalal[x]<lalal[y];}int sta[N];int get (int x,int y){    if (dep[x]<dep[y]) {  int tt=x;x=y;y=tt;}      for (int u=21;u>=0;u--)          if (dep[f[x][u]]>=dep[y])              x=f[x][u];      if (x==y) return x;      for (int u=21;u>=0;u--)          if (f[x][u]!=f[y][u])              x=f[x][u],y=f[y][u];      return f[x][0];  }int t;void bt ()//建立虚树 {    cnt=1;sta[cnt]=1;    for (int u=1;u<=t;u++)    {        int lca=get(a[u],sta[cnt]);        if (lca==sta[cnt]) sta[++cnt]=a[u];        else        {            while (true)            {                int x=sta[cnt],xx=sta[cnt-1];cnt--;                if (xx==lca)                {                    init(xx,x);                    break;                }                if (dep[xx]<dep[lca])                {                    init(lca,x);                    sta[++cnt]=lca;                    break;                }                init(xx,x);            }            sta[++cnt]=a[u];        }    }    for (int u=1;u<cnt;u++) init(sta[u],sta[u+1]);}int tot1[N];LL ans;void solve (int x){    int sum=0;    for (int u=last[x];u!=-1;u=e[u].last)    {        int y=e[u].y;        solve(y);        sum=sum+tot1[y];    }    if (tot1[x]==1) ans=ans+sum*s[x].step;    for (int u=last[x];u!=-1;u=e[u].last)    {        int y=e[u].y;        ans=ans+(LL)tot1[y]*(sum-tot1[y])*s[x].step;        sum=sum-tot1[y];        tot1[x]+=tot1[y];tot1[y]=0;    }    last[x]=-1;    return ;}inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){  if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){  x=x*10+ch-'0';ch=getchar();}    return x*f;}int main(){    tot=Last=1;    n=read();m=read();    scanf("%s",ss+1);    for (int u=n;u>=1;u--)     {        ins(ss[u]-'a');        pos[u]=Last;    /*  printf("%d %d\n",u,pos[u]);        system("pause");*/    }    num=0;memset(last,-1,sizeof(last));    for (int u=2;u<=tot;u++)    init(s[u].pre,u);    dep[0]=0;cnt=0;dfs(1,0);    memset(last,-1,sizeof(last));    for (int u=1;u<=m;u++)    {        num=0;        t=read();        for (int u=1;u<=t;u++)        {            int x=read();            a[u]=pos[x];            tot1[a[u]]=1;        }        sort(a+1,a+1+t,cmp);        int ttt=1;        for (int u=2;u<=t;u++)            if (a[u]!=a[ttt])                a[++ttt]=a[u];        t=ttt;        bt();        ans=0;        solve(1);tot1[1]=0;        printf("%lld\n",ans);    }    return 0;}