[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\n",ans);

    return 0;

}