并不对劲的bzoj4231: 回忆树

曾经终败给现在 2023-08-17 16:46 98阅读 0赞

#### 题目大意 ####

\\(n\\)个点的树，每条边上有一个小写字母。  
操作：给定2个点\\(u\\)，\\(v\\)（\\(u\\)可能等于\\(v\\)）和一个非空字符串\\(s\\)，问从\\(u\\)到\\(v\\)的简单路径上的所有边按照到\\(u\\)的距离从小到大的顺序排列后，边上的字符依次拼接形成的字符串中给定的串\\(s\\)出现了多少次。  
\\(n,m\\leq 10^5,\\sum|s|<=3\\times 10^5\\)

#### 题解 ####

##### 离线 #####

当\\(u->v\\)路径上的字符组成的串的子串匹配上询问串时，记\\(x\\)为\\(u,v\\)的lca，则有三种可能：1.该子串在路径\\(u->x\\)上；2.该子串经过点\\(x\\)；3.该子串在路径\\(x->v\\)上。  
第二种情况可以暴力kmp。因为每个询问拿出来暴力kmp的链的长度不超过询问串长度的两倍，所以暴力kmp的总时间复杂度是\\(\\Theta(\\sum |s|)\\)  
考虑把情况一拆成\\(根->u\\)减去\\(根->x\\)。  
问题转化为如何在比较短的总时间内处理一些“根到某点的路径上出现了多少个询问串”的询问。  
在普通的匹配问题中，在AC自动机上每走过一个点，这个点的fail树祖先中关键点的贡献都+1。也就是说，AC自动机上一个点（对应询问串）的贡献（对应在大串上与之匹配的串的个数）为它fail树后代中被走过的点的个数。对fail树按DFS序剖分，可以用树状数组记录一个点子树中被走过的点。  
这题可以将询问离线，将询问串建AC自动机，将“根到某点\\(k\\)的路径上出现了多少个询问串”的询问放在\\(k\\)上。  
树上DFS的同时在AC自动机上匹配，回溯时也要在AC自动机上消去贡献。每走到一个点，在AC自动机上计算放在这个点的询问的答案。  
总时间复杂度\\(\\Theta((n+m)log \\space (\\sum|s|))\\)。  
情况三同理。

##### 代码 #####

#include<algorithm>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<iomanip>
    #include<iostream>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #define rep(i,x,y) for(register int i=(x);i<=(y);++i)
    #define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
    #define re register
    #define maxn 100010
    #define maxm 200010
    #define maxl 300010
    #define cx(c) (c-'a')
    #define xc(x) (x+'a')
    using namespace std;
    inline int read()
    {
        int x=0,f=1;
        char ch=getchar();
        while(isdigit(ch)==0 && ch!='-')ch=getchar();
        if(ch=='-')f=-1,ch=getchar();
        while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
        return x*f;
    }
    inline void write(int x)
    {
        int f=0;char ch[20];
        if(!x){puts("0");return;}
        if(x<0){putchar('-');x=-x;}
        while(x)ch[++f]=x%10+'0',x/=10;
        while(f)putchar(ch[f--]);
        putchar('\n');
    }
    int v[maxm],nxt[maxm],w[maxm],fir[maxn],tofa[maxn],cnte,kmps[maxl],kmpS[maxn];
    int mk[maxm][2],lca[maxm],ans[maxm],anc[maxn][18],dep[maxn],kmpf[maxl];
    int n,q;
    typedef struct que{int fh,nd,id,tp;}qs;
    qs makeq(int a1,int a2,int a3,int a4){qs tmp;tmp.fh=a1,tmp.nd=a2,tmp.id=a3,tmp.tp=a4;return tmp;}
    vector<qs>Q[maxn];
    void ade(int u1,int v1,int w1){v[cnte]=v1,w[cnte]=w1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
    struct AC
    {
        int ch[maxl][26],tr[maxl],dfn[maxl],cntnd,fa[maxl];
        int fir[maxl],nxt[maxl],v[maxl],cnte,tim,siz[maxl];
        char s[maxl];
        queue<int>q;
        void ade(int u1,int v1){v[cnte]=v1,nxt[cnte]=fir[u1],fir[u1]=cnte++;}
        int extend(int len)
        {
            int u=0;
            rep(i,1,len)
            {
                if(!ch[u][cx(s[i])])ch[u][cx(s[i])]=++cntnd;
                u=ch[u][cx(s[i])];
            }
            return u;
        }
        void getfa()
        {
            rep(i,0,25)if(ch[0][i])q.push(ch[0][i]),fa[ch[0][i]]=0;
            while(!q.empty())
            {
                int u=q.front();q.pop();
                rep(i,0,25)
                {
                    if(!ch[u][i])ch[u][i]=ch[fa[u]][i];
                    else fa[ch[u][i]]=ch[fa[u]][i],q.push(ch[u][i]);
                }
            }
            rep(i,1,cntnd)ade(fa[i],i);
        }
        void getdf(int u){dfn[u]=++tim;siz[u]=1;for(int k=fir[u];k!=-1;k=nxt[k])getdf(v[k]),siz[u]+=siz[v[k]];}
        inline int lt(int x){return x&(-x);}
        void add(int x,int k){for(;x<=tim;x+=lt(x))tr[x]+=k;}
        int ask(int x){int k=0;for(;x;x-=lt(x))k+=tr[x];return k;} 
        int query(int u){return ask(dfn[u]+siz[u]-1)-ask(dfn[u]-1);}
      
    }t[2];
    void getf(int u)
    {
        rep(i,1,17)anc[u][i]=anc[anc[u][i-1]][i-1];
        for(int k=fir[u];k!=-1;k=nxt[k])
        {
            if(v[k]!=anc[u][0])
            {
                anc[v[k]][0]=u,dep[v[k]]=dep[u]+1,tofa[v[k]]=w[k];
                getf(v[k]);
            }
        }
    }
    int Lca(int x,int y)
    {
        if(dep[y]>dep[x])swap(x,y);
        dwn(i,17,0)if(dep[anc[x][i]]>=dep[y]&&anc[x][i])x=anc[x][i];
        if(x==y)return x;
        dwn(i,17,0)if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
        return anc[x][0]; 
    }
    int getkmp(int id,int len,int nd0,int nd1)
    {
        int Len=min(dep[mk[id][0]]-dep[lca[id]],len-1)+min(dep[mk[id][1]]-dep[lca[id]],len-1);
        int x[2],hd=0,tl=Len,nds[2];nds[0]=nd0,nds[1]=nd1;
        rep(i,0,1){x[i]=mk[id][i];dwn(j,17,0)if(dep[anc[x[i]][j]]-dep[lca[id]]>=len-1&&anc[x[i]][j])x[i]=anc[x[i]][j];}
        rep(i,0,1)if(dep[mk[id][i]]-dep[lca[id]]>=len)Q[x[i]].push_back(makeq(-1,nds[i],id,i));
        while(x[0]!=lca[id])kmpS[tl--]=tofa[x[0]],x[0]=anc[x[0]][0];
        while(x[1]!=lca[id])kmpS[++hd]=tofa[x[1]],x[1]=anc[x[1]][0];
        return Len;
    }
    int fa[maxn];
    int kmp(int len,int Len)
    {
        fa[1]=0;int hd=0;
        if(len>Len){rep(i,1,len)kmps[i]=0;return 0;}
        rep(i,1,len-1)
        {
            while(hd&&kmps[i+1]!=kmps[hd+1])hd=fa[hd];
            if(kmps[i+1]!=kmps[hd+1])fa[i+1]=hd;
            else fa[i+1]=++hd;
        }
        int u=0,res=0;
        rep(i,1,Len)
        {
            while(kmps[u+1]!=kmpS[i]&&u)u=fa[u];
            if(kmps[u+1]!=kmpS[i])u=0;
            else u++;
            res+=(u==len);
        }
        rep(i,1,len)kmps[i]=fa[i]=0;
        return res;
    }
    void getans(int u,int nd0,int nd1)
    {
        int nd[2],lim=Q[u].size();nd[0]=nd0,nd[1]=nd1;
        rep(i,0,lim-1)ans[Q[u][i].id]+=Q[u][i].fh* t[Q[u][i].tp].query(Q[u][i].nd);
        for(int k=fir[u];k!=-1;k=nxt[k])
        {
            if(v[k]!=anc[u][0])
            {
                rep(i,0,1)t[i].add(t[i].dfn[t[i].ch[nd[i]][w[k]]],1);
                getans(v[k],t[0].ch[nd0][w[k]],t[1].ch[nd1][w[k]]);
                rep(i,0,1)t[i].add(t[i].dfn[t[i].ch[nd[i]][w[k]]],-1);
            }
        }
    }
    int main()
    {
        n=read(),q=read();
        memset(fir,-1,sizeof(fir));
        rep(i,0,1)memset(t[i].fir,-1,sizeof(t[i].fir));
        rep(i,1,n-1)
        {
            int x=read(),y=read();char c=getchar();
            ade(x,y,cx(c)),ade(y,x,cx(c)); 
        }
        getf(1);
        rep(i,1,q)
        {
            mk[i][1]=read(),mk[i][0]=read();scanf("%s",t[0].s+1);
            if(mk[i][1]==mk[i][0]){ans[i]=0;continue;}
            lca[i]=Lca(mk[i][0],mk[i][1]);
            int len=strlen(t[0].s+1),nd[2]; 
            rep(j,1,len)t[1].s[j]=t[0].s[len-j+1],kmps[j]=cx(t[0].s[j]);
            rep(j,0,1){if(dep[mk[i][j]]-dep[lca[i]]>=len)nd[j]=t[j].extend(len),Q[mk[i][j]].push_back(makeq(1,nd[j],i,j));}
            ans[i]=kmp(len,getkmp(i,len,nd[0],nd[1]));
        }
        rep(i,0,1)t[i].getfa(),t[i].getdf(0);
        getans(1,0,0);
        rep(i,1,q)write(ans[i]);
        return 0;
    }

##### 在线 #####

很遗憾，并不对劲的人在还有资源的时候太菜了。

#### 一些感想 ####

（想到）在线做法（的人）太强了！

转载于:https://www.cnblogs.com/xzyf/p/11311647.html