【BZOJ3926】【ZJOI2015】—诸神眷顾的幻想乡（广义后缀自动机）

传送门

---

考虑怎么样才能构造出匹配所有字符的后缀自动机
发现显然问题出在树上分叉处，需要分别对几个儿子构造
而方向不同会导致问题

但是这道题保证叶子结点不到$20$个
从每个叶子节点开始$dfs$一次，对所有串建一个广义$Sam$即可
注意构建方式，每个儿子继承父亲的$last$

而$Sam$上一个点对应子串个数就是$len[i]-len[fa[i]]$

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<21|1;
inline char gc(){
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
    return (ib==ob)?EOF:*ib++;
} 
#define gc getchar
inline int read(){
    char ch=gc();
    int res=0,f=1;
    while(!isdigit(ch))f^=ch=='-',ch=gc();
    while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
    return f?res:-res;
}
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define bg begin
#define re register
const int N=4000005;
int nxt[N][12],len[N],fa[N],tot;
inline int insert(int c,int last){
    int cur=++tot,p=last;len[cur]=len[p]+1;
    for(;p&&!nxt[p][c];p=fa[p])nxt[p][c]=cur;
    if(!p)fa[cur]=1;
    else{
        int q=nxt[p][c];
        if(len[p]+1==len[q])fa[cur]=q;
        else {
            int clo=++tot;
            memcpy(nxt[clo],nxt[q],sizeof(nxt[q]));
            fa[clo]=fa[q],len[clo]=len[p]+1;
            fa[q]=fa[cur]=clo;
            for(;p&&nxt[p][c]==q;p=fa[p])nxt[p][c]=clo;
        }
    }return cur;
}
const int M=200005;
int n,c;
int in[M],val[M];
vector<int>e[M];
void dfs(int u,int f,int last){
    int p=insert(val[u],last);
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==f)continue;
        dfs(v,u,p);
    }
}
int main(){
    n=read(),c=read();tot=1;
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        e[u].pb(v),e[v].pb(u),in[u]++,in[v]++;
    }
    for(int i=1;i<=n;i++)if(in[i]==1)dfs(i,0,1);
    ll res=0;
    for(int i=1;i<=tot;i++)
        res+=len[i]-len[fa[i]];
    cout<<res;
}