bzoj 3926 转换+广义后缀自动机

时间：2024-03-20 22:03:02

思路：重点在于叶子节点只有20个，我们把叶子节点提到根，把20个trie图插入后缀自动机，然后就是算有多少个本质不同的字串。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mk make_pair

#define PII pair<int, int>

#define PLI pair<LL, int>

#define ull unsigned long long

using namespace std;

const int N = 2e6 + ;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + ;

const double eps = 1e-;

int n, m, c, tot, s[N], deg[N], head[N];

struct Edge {

    int to, nx;

} edge[N];

void add(int u, int v) {

    edge[tot].to = v;

    edge[tot].nx = head[u];

    head[u] = tot++;

}

struct SuffixAutomaton {

    int last, cur, cnt, ch[N<<][], id[N<<], fa[N<<], dis[N<<], sz[N<<], c[N];

    SuffixAutomaton() {cur = cnt = ;}

    void init() {

        for(int i = ; i <= cnt; i++) {

            memset(ch[i], , sizeof(ch[i]));

            sz[i] = c[i] = dis[i] = fa[i] = ;

        }

        cur = cnt = ;

    }

    int extend(int p, int c) {

        cur = ++cnt; dis[cur] = dis[p]+;

        for(; p && !ch[p][c]; p = fa[p]) ch[p][c] = cur;

        if(!p) fa[cur] = ;

        else {

            int q = ch[p][c];

            if(dis[q] == dis[p]+) fa[cur] = q;

            else {

                int nt = ++cnt; dis[nt] = dis[p]+;

                memcpy(ch[nt], ch[q], sizeof(ch[q]));

                fa[nt] = fa[q]; fa[q] = fa[cur] = nt;

                for(; ch[p][c]==q; p=fa[p]) ch[p][c] = nt;

            }

        }

        sz[cur] = ;

        return cur;

    }

    void getSize(int n) {

        for(int i = ; i <= cnt; i++) c[dis[i]]++;

        for(int i = ; i <= n; i++) c[i] += c[i-];

        for(int i = cnt; i >= ; i--) id[c[dis[i]]--] = i;

    }

    void dfs(int u, int fa, int last) {

        int cur = extend(last, s[u]);

        for(int i = head[u]; ~i; i = edge[i].nx) {

            int v = edge[i].to;

            if(v != fa) dfs(v, u, cur);

        }

    }

    void solve() {

        memset(head, -, sizeof(head));

        scanf("%d%d", &n, &c);

        for(int i = ; i <= n; i++) scanf("%d", &s[i]);

        for(int i = ; i < n; i++) {

            int u, v; scanf("%d%d", &u, &v);

            add(u, v); add(v, u);

            deg[u]++; deg[v]++;

        }

        for(int i = ; i <= n; i++)

            if(deg[i] == ) dfs(i, , );

        LL ans = ;

        for(int i = ; i <= cnt; i++)

            ans += dis[i] - dis[fa[i]];

        printf("%lld\n", ans);

    }

} sam;

int main() {

    sam.solve();

    return ;

}

/*

*/

相关文章