bzoj4713: 迷失的字符串

Description

有一棵n个节点的大树，上面每条边有一个小写字符。

对于任意两个不同的点u,v，我们可以在树上找到u出发到v终止的唯一的一条最短路径，并将沿途经过的边上的字符依次写下来，得到一个字符串。

对于一个字符串，如果存在这样一个点对(u,v)，使得它们路径上的字符串与其完全匹配，那么我们就称这个字符串属于这棵树。

现在有m个迷失的字符串，请你写一个程序帮助判断每一条字符串是否属于这棵树。

Input

第一行包含一个正整数n(2<=n<=30000)，表示树的点数。

接下来n-1行每行包含两个正整数a,b和一个小写字符c(1<=a,b<=n,a!=b)，表示a点到b点之间有一条无向的树边，上面写着字符c。

接下来一行包含一个正整数m(1<=m<=30000)，表示迷失的字符串的个数。

接下来m行，每行一个由小写字符组成的字符串，分别表示每个迷失的字符串。

输入数据保证所有迷之的字符串的长度之和不超过30000。

Output

包含m行，对于第i行，如果在树上可以找到第i个字符串，输出YES，否则输出NO。

对单独一个串可以dp，f[w][i]表示从下往上走到w这条边，是否能匹配到第i个字符，合并原串和反串的答案可以确定原串是否在树上出现，复杂度为O(n*串长)

可以用bitset优化，同时对所有串进行dp，复杂度降为O(n*总串长/32)，可以通过此题

#include<bits/stdc++.h>
typedef unsigned int u32;
typedef u32 bits[945];
const int N=30007;
int n,m;
int es[N*2],enx[N*2],ev[N*2],e0[N],ep=2,ls[N];
char s0[N];
int p1=1,p2=0,mx;
bits v1[26],v2[26],u1[26],u2[26],f1[N],f2[N],ans,ans1,ans2;
void set1(bits a,u32 x){a[x>>5]|=1<<(x&31);}
u32 test(bits a,u32 x){return a[x>>5]>>(x&31)&1;}
void ors(bits a,bits b){for(int i=0;i<=mx;i+=2)a[i]|=b[i],a[i+1]|=b[i+1];}
void chk(bits a,bits b,bits c){for(int i=0;i<=mx;i+=2)ans[i]|=a[i]&b[i],ans[i+1]|=a[i+1]&b[i+1];}
void cal1(bits a,bits v,bits u){
    for(int i=mx;i;--i)a[i]=(a[i]<<1|a[i-1]>>31)&v[i]|u[i];
    a[0]=a[0]<<1&v[0]|u[0];
}
void cal2(bits a,bits v,bits u){
    a[mx+1]=0;
    for(int i=0;i<=mx;++i)a[i]=(a[i]>>1|a[i+1]<<31)&v[i]|u[i];
}
void dfs(int w,int pa,int c=-1){
    for(int i=e0[w];i;i=enx[i]){
        int u=es[i];
        if(u!=pa){
            dfs(u,w,ev[i]);
            chk(f1[w],f2[u],ans);
            chk(f2[w],f1[u],ans);
            ors(f1[w],f1[u]);
            ors(f2[w],f2[u]);
        }
    }
    if(c==-1)return;
    cal1(f1[w],v1[c],u1[c]);
    cal2(f2[w],v2[c],u2[c]);
    ors(ans1,f1[w]);
    ors(ans2,f2[w]);
}
int main(){
    scanf("%d",&n);
    for(int i=1,a,b;i<n;++i){
        char c;
        scanf("%d%d %c",&a,&b,&c);
        es[ep]=b;enx[ep]=e0[a];ev[ep]=c-'a';e0[a]=ep++;
        es[ep]=a;enx[ep]=e0[b];ev[ep]=c-'a';e0[b]=ep++;
    }
    scanf("%d",&m);
    for(int i=0;i<m;++i){
        scanf("%s",s0+1);
        int l=strlen(s0+1);
        set1(u1[s0[1]-'a'],++p1);
        ls[i]=p1;
        for(int i=2;i<=l;++i)set1(v1[s0[i]-'a'],++p1);
        for(int i=1;i<l;++i)set1(v2[s0[i]-'a'],++p2);
        set1(u2[s0[l]-'a'],++p2);
    }
    ls[m]=p1+1;
    mx=p1/32+2;
    dfs(1,0);
    for(int i=0;i<m;++i){
        u32 d=test(ans1,ls[i+1]-1)|test(ans2,ls[i]-1);
        for(int j=ls[i];j<ls[i+1]-1;++j)d|=test(ans,j);
        puts(d?"YES":"NO");
    }
    return 0;
}