[ZJOI2015]诸神眷顾的幻想乡 广义后缀自动机+DFS+语文题

才知道题目中是只有20个叶子节点的意思QAQ....

这次的广义后缀自动机只是将 last 设为 1， 并重新插入.

相比于正统的写法，比较浪费空间.

Code:

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector> 
#define setIO(s) freopen(s".in","r",stdin)
#define maxn 3000000
#define ll long long

using namespace std;

ll ans; 
int head[maxn],to[maxn],nex[maxn],edges,de[maxn]; 
int n,C,val[maxn];
void addedge(int u,int v){
    nex[++edges]=head[u],head[u]=edges,to[edges]=v;     
} 
struct SAM{
    int tot,len[maxn],ch[maxn][11],f[maxn]; 
    void init(){ tot = 1; } 
    int extend(int c,int last){
        int np = ++tot,p = last; len[np] = len[last] + 1, last = tot; 
        while(p && !ch[p][c]) ch[p][c] = np,p = f[p];                        
        if(!p) f[np] = 1;
        else{
            int q = ch[p][c]; 
            if(len[q] == len[p] + 1) f[np] = q;
            else {
                int nq = ++tot;
                len[nq] = len[p] + 1; 
                memcpy(ch[nq],ch[q],sizeof(ch[q])); 
                f[nq] = f[q],f[q] = f[np] = nq;
                while(p && ch[p][c] == q) ch[p][c] = nq,p = f[p];
            }
        }  
        return last; 
    }
    void calc(){
        for(int i=1;i<=tot;++i) ans+=len[i]-len[f[i]]; 
    }
}sam; 
void DFS(int u,int fa,int t){
    t = sam.extend(val[u],t);
    for(int v=head[u];v;v=nex[v]){
        if(to[v]==fa) continue;
        DFS(to[v],u,t);
    }
}
int main(){
    //setIO("input");
    scanf("%d%d",&n,&C);
    for(int i=1;i<=n;++i) scanf("%d",&val[i]); 
    for(int i=1;i<n;++i){
        int a,b;
        scanf("%d%d",&a,&b);
        addedge(a,b),addedge(b,a);      
        ++de[a],++de[b]; 
    }
    sam.init(); 
    for(int i=1;i<=n;++i) if(de[i]==1) DFS(i,0,1); 
    sam.calc(); 
    printf("%lld
",ans); 
    return 0; 
}