cf917E. Upside Down | miaom's Blog
miaom's Blog

lych真的0

miaom's avatar miaom

cf917E. Upside Down

题目大意

给你$n$个节点的树,边上有字母。再给你$m$个字符串$S_i$。$q$次询问$x$到$y$的路经上的字母形成的字符串中,都多少个子串等于$S_z$。

$n,m,q,\sum|S_i|\le 100000$

题解

真的相当毒瘤的一道题。。不知道比赛里怎么A。。

首先容易想着点分治,接下来呢问题变成过重心有不过重心的两个部分,分别考虑解决。

方法1:分块(根本过不了)

我有一个分块的梦想!

先考虑不过重心的,由于不同的长度只有$\sqrt{\sum|S_i|}$种,对同样的长度在dfs时维护每个点到重心路径上该长度的字符串的hash值,并装到一个hash表里。询问时相当于询问某个点到根路径上某个hash值出现了几次,复杂度可能是$O(n\sqrt{n})$。

再考虑过重心的,发现完全不知道怎么搞,然后直接暴力判复杂度$O(\sum|S_{z_i}|)=O(n\max{|S_i|})$。

方法2:AC自动机+后缀自动机

既然分块行不通,就来点正常的字符串算法吧!

对于不过重心的,考虑建立$S_i$的AC自动机,每次dfs时在AC自动机上跑并对fail树上该点$+1$。询问时就是fail树上子树和。反串同理。

对于过重心的,会被重心分成一个前缀和一个后缀。考虑后缀树,相当于前缀在反串后缀树上某个点到根路经上,且后缀在后缀树上某个点到根路径上。这个点就是dfs时端点到重心构成的字符串自啊后缀树上的对应节点。

这部分可以离线处理,对每个$S_i$,考虑所有可能的前缀与后缀的组合对答案的贡献,相当于二维平面上区间加单点询问,使用线段树就能完成。

复杂度$O(n\log^2{n})$。

实现

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,m,q,len[N];char s[N];
int Nxt[N],Fst[N],Ans[N];//query
int used[N*2],to[N*2],nxt[N*2],str[N*2],fst[N],l=1;//edge
struct T
{
    int x,y,p;
}Q[N],Q0[N];//query
int sz[N],Mx[N],blg[N];
struct ACatm
{
    int c[N][26],fail[N],cnt,id[N];
    int s[N][26],st[N],ed[N],ly;
    int q[N];
    vector<int>v[N];
    void clr()
    {
        cnt=1;
    }
    void add(char s[],int len,int k)
    {
        int now=1;
        for (int i=0;i<len;i++)
        {
            if (!c[now][s[i]-'a']) c[now][s[i]-'a']=++cnt;
            now=c[now][s[i]-'a'];
        }
        id[k]=now;
        /**/
    }
    void dfs(int x)
    {
        st[x]=++ly;
        for (int i=0;i<v[x].size();i++)
            dfs(v[x][i]);
        ed[x]=ly;
    }
    void build()
    {
        for (int i=0;i<26;i++)
            c[0][i]=1;
        int l=0,r=1;
        q[1]=1;//fail[1]=0;
        while(l<r)
        {
            int x=q[++l];
            for (int i=0;i<26;i++)
                if (c[x][i])
                {
                    q[++r]=c[x][i];
                    fail[c[x][i]]=c[fail[x]][i];
                }
                else c[x][i]=c[fail[x]][i];
        }
        for (int i=2;i<=cnt;i++)
            v[fail[i]].push_back(i);
        dfs(1);
/*
        puts("=====");
        for (int i=1;i<=cnt;i++)
        {

            printf("%d----%d  %d-%d\n",i,fail[i],st[i],ed[i]);
        }
*/
    }

    int val[N*4];
    void add(int k,int l,int r,int x,int y)
    {
        val[k]+=y;
        if (l==r) return;
        int mid=l+r>>1;
        if (x<=mid) add(k<<1,l,mid,x,y);
        else add(k<<1|1,mid+1,r,x,y);
    }
    int qry(int k,int l,int r,int x,int y)
    {
        if (x<=l&&r<=y) return val[k];
        int mid=l+r>>1,ans=0;
        if (x<=mid) ans+=qry(k<<1,l,mid,x,y);
        if (y>mid) ans+=qry(k<<1|1,mid+1,r,x,y);
        return ans;
    }
    void add(int x,int y)
    {
        //x+=y
        //cerr<<st[x]<<"***"<<y<<endl;
        add(1,1,cnt,st[x],y);
    }
    int qry(int x)
    {
        x=id[x];
        //cerr<<x<<endl;
        //cerr<<st[x]<<' '<<ed[x]<<endl;
        return qry(1,1,cnt,st[x],ed[x]);
    }
}A1,A2;
struct S
{
    int x,y,flag;
}newS=(S){1,0,0};
struct SAM
{
    int F[N*2],st[N*2],c[N*2][26],cnt;
    int pos[N*2],str[N],ly,s[N*2][26];
    vector<int>v[N];
    int stt[N*2],ed[N*2],hz;
    void clr()
    {
        cnt=1;
    }
    int add(int p,int x,int y)
    {
        int q,np,nq;
        if (c[p][x]&&st[c[p][x]]==st[p]+1)
            return c[p][x];
        st[np=++cnt]=st[p]+1;pos[np]=y;
        while(p&&!c[p][x]) c[p][x]=np,p=F[p];
        if (!p) F[np]=1;
        else if (st[p]+1==st[q=c[p][x]]) F[np]=q;
        else
        {
            if (st[np]==st[p]+1)
            {
                nq=np;st[nq]=st[p]+1;
                for (int i=0;i<26;i++) c[nq][i]=c[q][i];
                F[nq]=F[q];F[q]=nq;
                while(p&&c[p][x]==q) c[p][x]=nq,p=F[p];
            }
            else
            {
                st[nq=++cnt]=st[p]+1;pos[nq]=pos[q];
                for (int i=0;i<26;i++) c[nq][i]=c[q][i];
                F[nq]=F[q];F[q]=F[np]=nq;
                while(p&&c[p][x]==q) c[p][x]=nq,p=F[p];
            }
        }
        return np;
    }
    void add(char s[],int len,int k)
    {
        int now=1;
        for (int i=0;i<len;i++)
        {
            str[++ly]=s[i]-'a';
            now=add(now,s[i]-'a',ly);
        }/*
        puts("-------");
        for (int i=1;i<=cnt;i++)
            printf("%d  %d %d %d %d\n",i,F[i],st[i],c[i][0],c[i][1]);*/
    }
    void dfs(int x)
    {
        //cerr<<x<<endl;
        stt[x]=++hz;
        for (int i=0;i<v[x].size();i++)
            dfs(v[x][i]);
        ed[x]=hz;
    }
    void build()
    {
        /*suffix tree*/
        for (int i=2;i<=cnt;i++)
        {
            //cerr<<i<<' '<<F[i]<<' '<<str[pos[i]-st[i]+1]<<endl;
            pos[i]=pos[i]-st[F[i]];
            s[F[i]][str[pos[i]]]=i;
            v[F[i]].push_back(i);
        }
        dfs(1);
/*
        puts("=============");
        for (int i=1;i<=ly;i++)
            putchar(str[i]+'a');
        puts("");
        for (int i=1;i<=cnt;i++)
        {
            printf("%d    %d %d %c\n",i,F[i],st[i],str[pos[i]]+'a');
        }
*/
    }
    S Get(S x,int y)
    {
        if (x.flag==1) return x;
        if (x.y==0)
        {
            //cerr<<s[x.x][y]<<endl;
            if (!s[x.x][y]) x.flag=1;
            else x.x=s[x.x][y],x.y=st[x.x]-st[F[x.x]]-1;
        }
        else
        {
            if (str[pos[x.x]-(st[x.x]-st[F[x.x]])+x.y]!=y) x.flag=1;
            else x.y--;
        }
        return x;
    }
}S1,S2;
void link(int x,int y,int z)
{
    to[++l]=y;nxt[l]=fst[x];fst[x]=l;str[l]=z;
    to[++l]=x;nxt[l]=fst[y];fst[y]=l;str[l]=z;
}
void Dfs(int x,int f)
{
    sz[x]=1;Mx[x]=0;
    for (int i=fst[x];i;i=nxt[i])
    if (!used[i]&&to[i]!=f)
    {
        Dfs(to[i],x);
        sz[x]+=sz[to[i]];
        Mx[x]=max(Mx[x],sz[to[i]]);
    }
}
void GetG(int x,int f,int &G,int size)
{
    if (max(Mx[x],size-sz[x])<max(Mx[G],size-sz[G])) G=x;
    for (int i=fst[x];i;i=nxt[i])
        if (!used[i]&&to[i]!=f) GetG(to[i],x,G,size);
}
void dfs(int x,int f,int y)
{
    blg[x]=y;
    for (int i=fst[x];i;i=nxt[i])
        if (!used[i]&&to[i]!=f)
            dfs(to[i],x,y);
}
int FST[N],NXT[N*2];//qry on ACatm
void work(int x,int n1,int n2,S m1,S m2,int f)
{
    //cerr<<x<<endl;
    //cerr<<x<<' '<<n1<<' '<<n2<<endl;
    A1.add(n1,1);
    A2.add(n2,1);

    for (int i=FST[x];i;i=NXT[i])
    {
        //cerr<<i<<endl;
        if (i&1)
        {
            Ans[i/2]+=A1.qry(Q[i/2].p);
            Q0[i/2].y=m2.y?S2.F[m2.x]:m2.x;
            //cout<<"x: "<<Q0[i/2].x<<' '<<m1.x<<' '<<m1.y<<endl;
        }
        else
        {
            Ans[i/2]+=A2.qry(Q[i/2].p);
            Q0[i/2].x=m1.y?S1.F[m1.x]:m1.x;
            //cout<<"y: "<<Q0[i/2].y<<endl;
        }
    }

    for (int i=fst[x];i;i=nxt[i])
    if (!used[i]&&to[i]!=f)
    {
        //cerr<<(char)(str[i]+'a')<<endl;
        work(to[i],A1.c[n1][str[i]],A2.c[n2][str[i]],S1.Get(m1,str[i]),S2.Get(m2,str[i]),x);
    }

    A1.add(n1,-1);
    A2.add(n2,-1);
}
void clrFST(int x,int f)
{
    FST[x]=0;
    for (int i=fst[x];i;i=nxt[i])
        if (!used[i]&&to[i]!=f)
            clrFST(to[i],x);
}
void solve(int x)
{
    int G=x;
    Dfs(x,0);
    GetG(x,0,G,sz[x]);
    //cerr<<x<<"   "<<G<<endl;

    for (int i=fst[G];i;i=nxt[i])
    if (!used[i])
        dfs(to[i],G,to[i]);
    swap(Fst[G],Fst[x]);
    for (int i=Fst[G],tmp;i;i=tmp)
    {
        //cerr<<"ok "<<i<<endl;
        tmp=Nxt[i];
        if (Q[i].x==G||Q[i].y==G)
        {
            //cerr<<"Skipped: "<<i<<endl;
            if (Q[i].x!=G) NXT[i*2]=FST[Q[i].x],FST[Q[i].x]=i*2;//A2
            if (Q[i].y!=G) NXT[i*2+1]=FST[Q[i].y],FST[Q[i].y]=i*2+1;//A1
            continue;
        }
        //cerr<<blg[Q[i].x]<<' '<<blg[Q[i].y]<<endl;
        if (blg[Q[i].x]==blg[Q[i].y])
        {
            //cerr<<blg[Q[i].x]<<endl;
            Nxt[i]=Fst[blg[Q[i].x]];
            Fst[blg[Q[i].x]]=i;
        }
        else
        {
            /*calc*/
            //cerr<<G<<"--"<<i<<endl;
            NXT[i*2]=FST[Q[i].x];FST[Q[i].x]=i*2;//A2
            NXT[i*2+1]=FST[Q[i].y];FST[Q[i].y]=i*2+1;//A1

            /**/
        }
    }
    /*dfs*/
    work(G,1,1,newS,newS,0);
    /*clear FST*/
    clrFST(G,0);
    //return;

    for (int i=fst[G];i;i=nxt[i])
    if (!used[i])
    {
        used[i]=used[i^1]=1;
        solve(to[i]);
    }
}
struct Md
{
    int x,l,r,p;
}md[N*2];
bool operator<(T a,T b){return a.x<b.x;}
bool operator<(Md a,Md b){return a.x<b.x;}
vector<T>v[N];
int val[N*8];
void mdy(int k,int l,int r,int x,int y,int p)
{
    if (x<=l&&r<=y)
    {
        val[k]+=p;
        return;
    }
    int mid=l+r>>1;
    if (x<=mid) mdy(k<<1,l,mid,x,y,p);
    if (y>mid) mdy(k<<1|1,mid+1,r,x,y,p);
}
int qry(int k,int l,int r,int x)
{
    if (l==r) return val[k];
    int mid=l+r>>1;
    if (x<=mid) return val[k]+qry(k<<1,l,mid,x);
    return val[k]+qry(k<<1|1,mid+1,r,x);
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d%s",&x,&y,s);
        link(x,y,s[0]-'a');
    }

    int sta[N],ly=0,strr[N];
    /**/
    A1.clr();S1.clr();
    A2.clr();S2.clr();

    for (int i=1;i<=m;i++)
    {
        scanf("%s",s);

        len[i]=strlen(s);

        sta[i]=ly+1;
        for (int j=0;j<len[i];j++)
        strr[++ly]=s[j]-'a';

        /*add to SAM*/
        S1.add(s,len[i],i);
        /*add to ACatm*/
        A1.add(s,len[i],i);

        reverse(s,s+len[i]);
        /*add to SAM*/
        S2.add(s,len[i],i);
        /*add to ACatm*/
        A2.add(s,len[i],i);


    }

    A1.build();S1.build();
    //return 0;
    A2.build();S2.build();

    for (int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&Q[i].x,&Q[i].y,&Q[i].p);
        Nxt[i]=i-1;
    }
    Fst[1]=q;

    solve(1);
/*
    for (int i=1;i<=q;i++)
        printf("%d    %d %d\n",Ans[i],S1.stt[Q0[i].x],S2.stt[Q0[i].y]);
*/
    //puts("------------------");
    /*calc on suffix tree*/
    for (int i=1;i<=q;i++)
    {
        //swap(Q0[i].x,Q0[i].y);
        if (S1.stt[Q0[i].x]&&S2.stt[Q0[i].y])
            v[Q[i].p].push_back((T){S1.stt[Q0[i].x],S2.stt[Q0[i].y],i});
    }
    int tmpx[N],tmpy[N];
    for (int i=1;i<=m;i++)
    {
        int m1=1,m2=1;
        for (int j=0;j<len[i];j++)
        {
            m1=S1.c[m1][strr[sta[i]+j]];
            tmpx[j+1]=m1;
        }
        for (int j=len[i]-1;j>=0;j--)
        {
            m2=S2.c[m2][strr[sta[i]+j]];
            tmpy[j]=m2;
        }
        int ly=0;
        //puts("ok");
        md[++ly]=(Md){0,1,S2.cnt,0};
        md[++ly]=(Md){S1.cnt+1,1,S2.cnt,0};
        //cerr<<i<<endl;
        for (int j=1;j<len[i];j++)
        {
            md[++ly]=(Md){S1.stt[tmpx[j]],S2.stt[tmpy[j]],S2.ed[tmpy[j]],1};
            md[++ly]=(Md){S1.ed[tmpx[j]]+1,S2.stt[tmpy[j]],S2.ed[tmpy[j]],-1};
//        cerr<<i<<"  ---  "<<S1.stt[tmpx[j]]<<' '<<S1.ed[tmpx[j]]<<' '<<S2.stt[tmpy[j]]<<' '<<S2.ed[tmpy[j]]<<endl;
        }
        sort(md+1,md+ly+1);
        sort(v[i].begin(),v[i].end());
        for (int j=1,k=0;j<=ly;)
        {
            int tmp=md[j].x;
            while(k<v[i].size()&&v[i][k].x<tmp)
                Ans[v[i][k].p]+=qry(1,1,S2.cnt,v[i][k].y),k++;
            while(j<=ly&&md[j].x==tmp)
                mdy(1,1,S2.cnt,md[j].l,md[j].r,md[j].p),j++;
        }
    }
    for (int i=1;i<=q;i++)
    {
        printf("%d\n",Ans[i]);
        //printf("%d    %d %d\n",Ans[i],S1.stt[Q0[i].x],S2.stt[Q0[i].y]);

    }
    //cerr<<"QAQ: "<<newS.x<<' '<<newS.y<<' '<<newS.flag<<endl;
    //cerr<<S1.Get(newS,0).x;
}