【BZOJ3926】【ZJOI2015】诸神眷顾的幻想乡 广义后缀自动机
wangyuchen
2018-03-24 14:33:39
## 题目：
[题目在这里](http://www.lydsy.com/JudgeOnline/problem.php?id=3926)
## 思路&做法：
[参考的题解](http://wjmzbmr.com/archives/zjoi-2015-day-1%E9%A2%98%E8%A7%A3/)
既然只有$20$个叶子节点， 那么可以从每个叶子节点往上建一颗$trie$树, 然后合并成一棵大的$trie$树， 然后构建广义后缀自动机。
$($ 实现起来就是dfs时把节点上的颜色加进广义后缀自动机$)$
再然后就统计一下就可以了$(ans += len[x] - len[fail[x])$
## 代码：
```cpp
#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;
}
```