BZOJ4477: [Jsoi2015]字符串树

【传送门：BZOJ4477】

---

简要题意：

给出一棵n个点的树，树上的边都代表一个字符串，给出Q个询问，每个询问输入x,y和字符串s，求出x到y的路径上以s为前缀的字符串个数

---

题解：

自己yy了一波可持久化字典树

将每条边的字符串放到深度更深的节点保存

对于x到y的路径，将rt[x]+rt[y]-2*rt[lca]就可以了，因为我们不需要lca到它父亲的字符串

本机RE，提交AC。。。怕是机子出毛病了

---

参考代码：

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

using namespace std;

struct trie

{

    int son[],c;

    trie()

    {

        c=;

        memset(son,,sizeof(son));

    }

}tr[];int trlen;

int rt[];

struct node

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

char st[];

int slen;

void Link(int &u1,int d)

{

    if(u1==) u1=++trlen;

    tr[u1].c=;

    if(d==slen) return ;

    d++;

    int y=st[d]-'a'+;

    Link(tr[u1].son[y],d);

}

void Merge(int &u1,int u2)

{

    if(u1==){u1=u2;return ;}

    if(u2==) return ;

    tr[u1].c+=tr[u2].c;

    for(int i=;i<=;i++) Merge(tr[u1].son[i],tr[u2].son[i]);

}

int f[][],bin[],dep[];

void dfs(int x)

{

    for(int i=;bin[i]<=dep[x];i++) f[x][i]=f[f[x][i-]][i-];

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=f[x][])

        {

            f[y][]=x;

            dep[y]=dep[x]+;

            Merge(rt[y],rt[x]);

            dfs(y);

        }

    }

}

int LCA(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=;i>=;i--)

    {

        if(dep[x]-dep[y]>=bin[i])

        {

            x=f[x][i];

        }

    }

    if(x==y) return x;

    for(int i=;i>=;i--)

    {

        if(dep[x]>=bin[i]&&f[x][i]!=f[y][i])

        {

            x=f[x][i];y=f[y][i];

        }

    }

    return f[x][];

}

char s[];int clen;

int findc(int u1,int u2,int u3,int d)

{

    int c=tr[u1].c+tr[u2].c-*tr[u3].c;

    if(c==) return ;

    if(d==clen) return c;

    d++;

    int y=s[d]-'a'+;

    return findc(tr[u1].son[y],tr[u2].son[y],tr[u3].son[y],d);

}

int main()

{

    bin[]=;for(int i=;i<=;i++) bin[i]=bin[i-]<<;

    int n;

    scanf("%d",&n);

    len=;memset(last,,sizeof(last));

    trlen=;memset(rt,,sizeof(rt));

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d%s",&x,&y,st+);slen=strlen(st+);

        ins(x,y);

        Link(rt[y],);

    }

    f[][]=;dep[]=;dfs();

    int Q;

    scanf("%d",&Q);

    for(int i=;i<=Q;i++)

    {

        int x,y;

        scanf("%d%d%s",&x,&y,s+);

        clen=strlen(s+);

        int lca=LCA(x,y);

        printf("%d\n",findc(rt[x],rt[y],rt[lca],));

    }

    return ;

}