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

题目:

题目在这里

思路&做法:

参考的题解

既然只有$20$个叶子节点, 那么可以从每个叶子节点往上建一颗$trie$树, 然后合并成一棵大的$trie$树, 然后构建广义后缀自动机。$($ 实现起来就是dfs时把节点上的颜色加进广义后缀自动机$)$

再然后就统计一下就可以了$(ans += len[x] - len[fail[x])$

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int N = 2000010;

long long Ans;

struct Suffix_Automaton
{   int nxt[N][10], fail[N], sz;
    int len[N];
    int root;

    Suffix_Automaton() { }

    inline int newnode(int l)
    {   memset(nxt[sz], 0, sizeof(nxt[sz]));
        fail[sz] = 0;
        len[sz] = l;
        return sz++;
    }

    inline void init()
    {   sz = 1;
        root = newnode(0);
    }

    int add(int c, int last)
    {   if(nxt[last][c])
        {   int p = last, q = nxt[p][c];
            if(len[q] == len[p]+1)
                return q;
            else
            {   int u = newnode(len[p] + 1);
                for(int i=0; i<10; i++) nxt[u][i] = nxt[q][i];
                fail[u] = fail[q];
                fail[q] = u;
                while(nxt[p][c] == q)
                {   nxt[p][c] = u;
                    p = fail[p];
                }
                return u;
            }
        }
        else
        {   int now = newnode(len[last] + 1);
            int p = last;
            while(p && !nxt[p][c])
            {   nxt[p][c] = now;
                p = fail[p];
            }
            if(!p) fail[now] = root;
            else
            {   int q = nxt[p][c];
                if(len[q] == len[p]+1)
                    fail[now] = q;
                else
                {   int u = newnode(len[p] + 1);
                    for(int i=0; i<10; i++) nxt[u][i] = nxt[q][i];
                    fail[u] = fail[q];
                    fail[q] = fail[now] = u;
                    while(nxt[p][c] == q)
                    {   nxt[p][c] = u;
                        p = fail[p];
                    }
                }
            }
            Ans += (long long) (len[now] - len[fail[now]]);
            return now;
        }
    }
} tzw;

int color[N];

int r[N];

struct edge
{   int from, to;
    edge() { }
    edge(int _1, int _2):from(_1), to(_2) { }
} edges[2*N];
int head[N], nxt[2*N], tot;

inline void init()
{   memset(head, -1, sizeof(head));
    tot = 0;
}

inline void Add_Edge(int x, int y)
{   edges[tot] = edge(x, y);
    nxt[tot] = head[x];
    head[x] = tot++;
    edges[tot] = edge(y, x);
    nxt[tot] = head[y];
    head[y] = tot++;
}

void dfs(int x, int fa, int last)
{   last = tzw.add(color[x], last);
    for(int i=head[x]; ~i; i=nxt[i])
    {   edge & e = edges[i];
        if(e.to != fa)
            dfs(e.to, x, last);
    }
}

int main()
{   int n, m;
    scanf("%d %d", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%d", &color[i]);
    tzw.init();
    init();
    for(int i=1; i<n; i++)
    {   int x, y;
        scanf("%d %d", &x, &y);
        Add_Edge(x, y);
        r[x]++, r[y]++;
    }
    for(int i=1; i<=n; i++)
        if(r[i] == 1) dfs(i, 0, tzw.root);
    printf("%lld\n", Ans);
    return 0;
}

发表于 2018-03-24 14:33:39 in 广义后缀自动机