BZOJ4477 JSOI2015字符串树（可持久化trie）

　　树上建可持久化trie即可，有点过于裸了。darkbzoj过了然而在bzoj一直wa，不知道哪有锅。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

int n,m,p[N],fa[N][],deep[N],root[N],t,cnt;

struct data{int to,nxt;char s[];

}edge[N<<];

struct data2{int x,ch[];

}tree[N*];

void addedge(int x,int y,char *s){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;memcpy(edge[t].s,s,sizeof(s));}

void ins(int &k,int p,char *s,int n)

{

    tree[++cnt]=tree[k],k=cnt;tree[k].x++;

    if (p==n) return;

    ins(tree[k].ch[s[p+]-'a'],p+,s,n);

}

int query(int k,int p,char *s,int n)

{

    if (!k) return ;

    if (p==n) return tree[k].x;

    return query(tree[k].ch[s[p+]-'a'],p+,s,n);

}

void dfs(int k)

{

    for (int i=p[k];i;i=edge[i].nxt)

    if (edge[i].to!=fa[k][])

    {

        fa[edge[i].to][]=k;

        deep[edge[i].to]=deep[k]+;

        root[edge[i].to]=root[k];

        ins(root[edge[i].to],,edge[i].s,strlen(edge[i].s+));

        dfs(edge[i].to);

    }

}

int lca(int x,int y)

{

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

    for (int j=;~j;j--) if (deep[fa[x][j]]>=deep[y]) x=fa[x][j];

    if (x==y) return x;

    for (int j=;~j;j--) if (fa[x][j]!=fa[y][j]) x=fa[x][j],y=fa[y][j];

    return fa[x][];

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4477.in","r",stdin);

    freopen("bzoj4477.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

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

    {

        int x=read(),y=read();

        char s[];scanf("%s",s+);

        addedge(x,y,s);

    }

    dfs();

    fa[][]=;

    for (int j=;j<;j++)

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

        fa[i][j]=fa[fa[i][j-]][j-];

    m=read();

    while (m--)

    {

        int x=read(),y=read();

        char s[];scanf("%s",s+);

        printf("%d\n",query(root[x],,s,strlen(s+))+query(root[y],,s,strlen(s+))-(query(root[lca(x,y)],,s,strlen(s+))<<));

    }

    return ;

}