## 【日常小测】最长公共前缀

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;
const int M = N << 1;

inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int c = 0) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}

class Suffix_Automaton{
int cnt=1,ch[N][26],fail[N],vis[N],dep[N],sum[N];
int tot,arr[N],que[N],len[N],fa[N][20],_hash[N];
vector<int> G[N]; LL ans_tmp;
public:
inline int insert(int t, int cc) {
if (ch[t][cc] && len[ch[t][cc]] == len[t] + 1) return ch[t][cc];
int tail = ++cnt; len[tail] = len[t] + 1;
while (!ch[t][cc] && t) ch[t][cc] = tail, t=fail[t];
if (!t) fail[tail] = 1;
else {
if (len[ch[t][cc]] == len[t] + 1) fail[tail] = ch[t][cc];
else {
int nw = ++cnt, w = ch[t][cc]; len[nw] = len[t]+1;
memcpy(ch[nw], ch[w], sizeof(ch[nw]));
fail[nw] = fail[w]; fail[w] = fail[tail] = nw;
for (;ch[t][cc]==w;t=fail[t]) ch[t][cc] = nw;
}
} return tail;
}
inline void Build_Fail_Tree() {
for (int i=2;i<=cnt;i++) Add_Edge(fail[i], i);
dfs(1, 1);
for (int j=1;j<20;j++) {
for (int i=1;i<=cnt;i++) {
fa[i][j] = fa[fa[i][j-1]][j-1];
}
}
}
inline LL solve(int nn) {
for (int i=1;i<=nn;i++) arr[i] = pos[read()];
sort(arr+1, arr+1+nn, [](const int &a, const int &b) {return id[a] < id[b];});
for (int i=1;i<=nn;i++) _hash[i] = arr[i];
int mm = nn; nn = unique(arr+1, arr+1+nn) - arr - 1;
for (int i=1;i<=nn;i++) sum[i] = 0;
for (int i=1,j=1;i<=mm;i++) {
while (arr[j] != _hash[i]) j++;
sum[j]++;
}
que[tot=1] = 1; int MX = 1;
for (int i=1,lca;i<=nn;i++) {
vis[arr[i]] = sum[i];
lca = LCA(que[tot], arr[i]);
while (dep[que[tot]] > dep[lca]) {
if (dep[que[tot-1]] >= dep[lca]) G[que[tot-1]].push_back(que[tot]);
else G[lca].push_back(que[tot]);
--tot;
}
if (que[tot] != lca) que[++tot] = lca;
if (arr[i] != que[tot]) que[++tot] = arr[i];
MX = max(MX, tot);
}
while (tot > 1) G[que[tot-1]].push_back(que[tot]), --tot;
ans_tmp = 0;
Get_Ans(1);
return ans_tmp;
}
private:
void dfs(int w, int f) {
static int id_count = 0;
id[w] = ++id_count;
fa[w][0] = f; dep[w] = dep[f] + 1;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
dfs(to[i], w);
}
}
}
int Get_Ans(int w) {
int ret = vis[w];
if (w > 1) ans_tmp += vis[w] * (vis[w] - 1ll) / 2 * len[w];
for (int i=G[w].size()-1,tmp;~i;i--) {
tmp = Get_Ans(G[w][i]);
ans_tmp += (LL)tmp * ret * len[w];
ret += tmp;
}
vis[w] = 0;
G[w].clear();
return ret;
}
inline int LCA(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
for (int i=19;~i;i--) if (dep[fa[a][i]] >= dep[b]) a = fa[a][i];
if (a == b) return a;
for (int i=19;~i;i--) if (fa[a][i] != fa[b][i]) a = fa[a][i], b = fa[b][i];
return fa[a][0];
}
}SAM;

void DFS(int w, int f, int t) {
pos[w] = t;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f) {
int nt = SAM.insert(t, col[i]);
DFS(to[i], w, nt);
}
}
}

int main() {
n = read(); char pat[10];
for (int i=1,u,v;i<n;i++) {
scanf("%s",pat+1);
Add_Edge(u, v, pat[1] - 'a');
}
DFS(1, 1, 1);
SAM.Build_Fail_Tree();
return 0;
}


## 【BZOJ 3926】[ZJOI2015] 诸神眷顾的幻想乡

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;
const int M = 2000000;
const int C = 10;

class Suffix_Automaton{
int ch[M][C],pre[M],len[M],cnt;
public:
inline int insert(int last, int t) {
int w = ++cnt; len[w] = len[last] + 1; pre[0] = -1;
for (;~last&&!ch[last][t];last=pre[last]) ch[last][t] = w;
if (~last) {
if (len[ch[last][t]] == len[last] + 1) {
pre[w] = ch[last][t];
} else {
int nw = ++cnt, tmp = ch[last][t];
len[nw] = len[last] + 1;
pre[nw] = pre[tmp]; pre[tmp] = pre[w] = nw;
memcpy(ch[nw],ch[tmp],sizeof(ch[nw]));
for (;~last&&ch[last][t]==tmp;last=pre[last]) ch[last][t] = nw;
}
} return w;
}
inline LL solve() {
LL ret = 0;
for (int i=1;i<=cnt;i++)
ret += len[i] - len[pre[i]];
return ret;
}
}SAM;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v) {
static int E = 1; in[u]++; in[v]++;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void DFS(int w, int f, int s) {
int rt = SAM.insert(s, col[w]);