[BZOJ3926][Zjoi2015]諸神眷顧的幻想鄉（廣義SAM）

如果任意選一個點為根，那麼對于一個點 u u ，不停地往下走，總會走到一個度數為11的點。

再注意到題目條件：度數為 1 1 的點不超過2020個。

這就意味着可以分别以每個度數為 1 1 的點為根，在Trie樹上建構字尾自動機。

在Trie樹上建構字尾自動機，加入點uu時，需要把 last l a s t 設為 u u 的父親對應的節點，其他操作與一般SAM無異。

全部建構後，本質不同的子串個數就是∑u{Maxlu−MaxlParentu}∑u{Maxlu−MaxlParentu}。

代碼：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = ; bool bo = ; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = ; else res = c - ;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << ) + (res << ) + (c - );
    return bo ? ~res +  : res;
}
typedef long long ll;
const int N =  + , M =  + , L =  + ;
struct cyx {
    int go[], maxl, fa;
    void init() {memset(go, , sizeof(go)); maxl = fa = ;}
} T[L];
int n, c, col[N], ecnt, nxt[M], adj[N], go[M], cnt[N], QAQ;
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; cnt[go[ecnt] = v]++;
    nxt[++ecnt] = adj[v]; adj[v] = ecnt; cnt[go[ecnt] = u]++;
}
int ins(int c, int lst) {
    int i = lst; T[lst = ++QAQ].init(); T[lst].maxl = T[i].maxl + ;
    for (; i && !T[i].go[c]; i = T[i].fa) T[i].go[c] = lst;
    if (!i) T[lst].fa = ; else {
        int j = T[i].go[c]; if (T[i].maxl +  == T[j].maxl)
            T[lst].fa = j; else {
            int p; T[p = ++QAQ] = T[j]; T[lst].fa = T[j].fa = p;
            T[p].maxl = T[i].maxl + ; for (; i && T[i].go[c] == j;
                i = T[i].fa) T[i].go[c] = p;
        }
    }
    return lst;
}
void dfs(int u, int fu, int lst) {
    int x = ins(col[u], lst); for (int e = adj[u], v; e; e = nxt[e])
        if ((v = go[e]) != fu) dfs(v, u, x);
}
int main() {
    int i, x, y; n = read(); c = read(); T[QAQ = ].init();
    for (i = ; i <= n; i++) col[i] = read();
    for (i = ; i < n; i++) x = read(), y = read(), add_edge(x, y);
    for (i = ; i <= n; i++) if (cnt[i] == ) dfs(i, , ); ll ans = ;
    for (i = ; i <= QAQ; i++) ans += T[i].maxl - T[T[i].fa].maxl;
    cout << ans << endl; return ;
}