bzoj 4598: [Sdoi2016]模式字符串

題目描述

給出n個結點的樹結構T，其中每一個結點上有一個字符，這里我們所說的字符只考慮大寫字母A到Z，再給出長度為m的模式串s，其中每一位仍然是A到z的大寫字母。

Alice希望知道，有多少對結點<u，v>滿足T上從u到V的最短路徑形成的字符串可以由模式串S重復若干次得到？

這里結點對<u，v>是有序的，也就是說<u，v>和<v，u>需要被區分。

所謂模式串的重復，是將若干個模式串S依次相接（不能重疊)。例如當S=PLUS的時候，重復兩次會得到PLUSPLUS，重復三次會得到PLUSPLUSPLUS，同時要注恿，重復必須是整數次的。例如當S=XYXY時，因為必須重復整數次，所以XYXYXY不能看作是S重復若干次得到的。

輸入輸出格式

輸入格式：

每一個數據有多組測試，

第一行輸入一個整數C，表示總的測試個數。

對于每一組測試來說：

第一行輸入兩個整數，分別表示樹T的結點個數n與模式長度m。結點被依次編號為1到n，

之后一行，依次給出了n個大寫字母（以一個長度為n的字符串的形式給出），依次對應樹上每一個結點上的字符（第i個字符對應了第i個結點)。

之后n-1行，每行有兩個整數u和v表示樹上的一條無向邊，之后一行給定一個長度為m的由大寫字母組成的字符串，為模式串S。

輸出格式：

給出C行，對應C組測試。

每一行輸出一個整數，表示有多少對節點<u,v>滿足從u到v的路徑形成的字符串恰好是模式串的若干次重復.

輸入輸出樣例

輸入樣例#1：?復制

1
11 4
IODSSDSOIOI
1 2
2 3
3 4
1 5
5 6
6 7
3 8
8 9
6 10
10 11
SDOI

輸出樣例#1：?復制

5

說明

1<=C<=10，3<=N<=1000000，3<=M<=1000000

題解

　　題解大概看懂一點了……就是說用hash+點分治……好討厭hash……總感覺還是半懂不懂……

　　考慮每一個分治點，從他延伸下去能形成長度為多少的前綴和后綴（不包含自己和包含自己），然后兩個兩兩組合起來計算答案

　　據說時間復雜度$O(Tnlogn)$，數據就是為了卡點分的，然而因為全世界都只有前三組數據……所以能A……

//minamoto
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1000003
#define ull unsigned long long
#define ll long long
#define p 2000001001
#define inf 1000000000
using namespace std;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
inline int read(){
    #define num ch-'0'
    char ch;bool flag=0;int res;
    while(!isdigit(ch=getchar()))
    (ch=='-')&&(flag=true);
    for(res=num;isdigit(ch=getchar());res=res*10+num);
    (flag)&&(res=-res);
    #undef num
    return res;
}
char sr[1<<21],z[30];int C=-1,Z;
inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
inline void print(ll x){
    if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
int n,m,T,n1,rt,head[N],Next[N<<1],ver[N<<1],tot,size[N],son[N],sz,sz1;
int st[N],st1[N],len[N],cnt[N],cnt1[N];
ull mi[N],a[N],a1[N],b[N],c[N],val[N],sum[N],sum1[N];
ll ans;
bool vis[N];char s[N];
inline void add(int u,int v){
    ver[++tot]=v,Next[tot]=head[u],head[u]=tot;
    ver[++tot]=u,Next[tot]=head[v],head[v]=tot;
}
void findrt(int u,int fa){
    size[u]=1,son[u]=0;
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(vis[v]||v==fa) continue;
        findrt(v,u);
        cmax(son[u],size[v]);
        size[u]+=size[v];
    }
    cmax(son[u],n1-size[u]);
    if(son[u]<son[rt]) rt=u;
}
void getdep(int u,int fa){
    if(b[len[u]]==sum[u]&&val[u]==a[1]) st[++sz]=u;
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];if(vis[v]||v==fa) continue;
        sum[v]=sum[u]*p+val[v];
        len[v]=len[u]+1;
        getdep(v,u);
    }
}
void getdep1(int u,int fa){
    if(c[len[u]]==sum1[u]&&val[u]==a1[1]) st1[++sz1]=u;
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(vis[v]||v==fa) continue;
        sum1[v]=sum1[u]*p+val[v];
        getdep1(v,u);
    }
}
void calc(int u){
    for(int i=0;i<=m;++i) cnt[i]=cnt1[i]=0;
    if(a[1]==val[u]) cnt[1]=1;
    if(a[m]==val[u]) cnt1[1]=1;
    if(m==1) ans+=cnt1[1];
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(vis[v]) continue;
        sz=0,len[v]=1,sum[v]=val[v];
        getdep(v,u);
        for(int j=1;j<=sz;++j){
            int t=st[j];int pos=m-(len[t]-1)%m-1;
            if(pos==0) pos+=m;
            ans+=(ll)cnt1[pos];
        }
        sz1=0,sum1[v]=val[v];
        getdep1(v,u);
        for(int j=1;j<=sz1;++j){
            int t=st1[j];int pos=m-(len[t]-1)%m-1;
            if(pos==0) pos+=m;
            ans+=(ll)cnt[pos];
        }
        for(int j=1;j<=sz;++j){
            int t=st[j];int pos=(len[t])%m+1;
            if(val[u]==a[pos]) ++cnt[pos];
        }
        for(int j=1;j<=sz1;++j){
            int t=st1[j];int pos=(len[t])%m+1;
            if(val[u]==a1[pos]) ++cnt1[pos];
        }
    }
}
void solve(int u){
    calc(u),vis[u]=1;int totsz=size[u];
    for(int i=head[u];i;i=Next[i]){
        int v=ver[i];
        if(vis[v]) continue;
        rt=0;
        n1=size[v];
        if(n1<m) continue;
        findrt(v,u);
        solve(rt);
    }
}
int main(){
    T=read(),mi[0]=1;
    for(int i=1;i<=1000000;++i) mi[i]=mi[i-1]*p;
    while(T--){
        n=read(),m=read(),tot=0,ans=0;
        memset(head,0,sizeof(head));
        scanf("%s",s+1);
        for(int i=1;i<=n;++i) val[i]=s[i]-'A'+1;
        for(int i=1;i<n;++i){
            int u=read(),v=read();add(u,v);
        }
        scanf("%s",s+1);
        for(int i=1;i<=max(n,m);++i) a[i]=s[(i-1)%m+1]-'A'+1;
        for(int i=1;i<=max(n,m);++i) b[i]=b[i-1]+a[i]*mi[i-1];
        for(int i=1;i<=m;++i) a1[m-i+1]=a[i];
        for(int i=1;i<=max(n,m);++i) a1[i]=a1[(i-1)%m+1];
        for(int i=1;i<=max(n,m);++i) c[i]=c[i-1]+a1[i]*mi[i-1];
        memset(vis,0,sizeof(vis));
        son[0]=inf,rt=0,n1=n;
        findrt(1,0);
        solve(rt);
        print(ans);
    }
    Ot();
    return 0;
}

?