bzoj 3926 [Zjoi2015]诸神眷顾的幻想乡

发表于   |   分类于 ，   |  

Descripiton

给定一棵树，每个节点有一个字符，求从一个节点出发沿最短路径走到另一个节点所构成的字符串一共有多少种
注意：叶子数$\le$20

Solution

这个题，发现叶子数很少就很好做了，以每个叶子为根节点建立SAM即可，这样原树上所有路径都在SAM出现过,统计即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
const int N = 100005 * 2 * 20, M = 10;
typedef long long LL;
#define pb push_back
struct SAM {
    int tot, last, step[N], g[N], par[N], son[N][M], cnt[N], Q[N], ch[N], f[N];
    void init() {
        tot = 0;
        memset(par, 0, sizeof(par));
        par[0] = -1;
        memset(son, 0, sizeof(son));
    }
    int add(int last, int x) {
        int p = last, np = ++tot;
        step[np] = step[p] + 1, last = np, ++g[np];//right
        ch[np] = x;
        for (; !son[p][x] && ~p; p = par[p])    son[p][x] = np;
        if (p == -1)    return np;
        int q = son[p][x];
        if (step[q] == step[p] + 1) par[np] = q;
        else {
            step[++tot] = step[p] + 1;
            ch[tot] = x;
            int nq = tot;
            memcpy(son[nq], son[q], sizeof(son[q]));
            par[nq] = par[q];
            par[np] = par[q] = nq;
            for (; son[p][x] == q && ~p; p = par[p])    son[p][x] = nq;
        }
        return np;
    }
    void topo() {
        for (int i = 1; i <= tot; ++i)    ++cnt[step[i]];
        for (int i = 1; i <= tot; ++i)    cnt[i] += cnt[i - 1];
        for (int i = 1; i <= tot; ++i)    Q[cnt[step[i]]--] = i;        
    }
    LL gao() {
        LL ans = 0;
        for (int i = 1; i <= tot; ++i)  ans += step[i] - step[par[i]];//i状态表示多少个字符串
        return ans;
    }
}S;
int a[100005], d[100005];
vector<int> g[100005];
void dfs(int u, int fa, int last) {
    int t = S.add(last, a[u]);
    for (int i = 0; i < g[u].size(); ++i) {
        int v = g[u][i];
        if (v == fa)    continue;
        dfs(v, u, t);
    }
}
int main() {
    S.init();
    int n, c;
    scanf("%d%d", &n, &c);
    for (int i = 1; i <= n; ++i)    scanf("%d", &a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        g[u].pb(v), g[v].pb(u);
        ++d[u], ++d[v];
    }
    for (int i = 1; i <= n; ++i)
        if (d[i] == 1)  dfs(i, 0, 0);
    printf("%lld\n", S.gao());
    return 0;
}