BZOJ 3926 广义后缀自动机
BZOJ 3926 广义后缀自动机
给一棵树，点上有字母，问树上路径组成的本质不同的字符串有多少个。
$ n\le10^5,|\Sigma|\le10, |\text {leaves}| \le 20 $ .
Sol.
很久之前就会做……直到今天才来打……
打题半小时调题两小时……
注意到叶子特别少，以每个叶子为根的 trie 合并成一棵打 trie 后所有树上路径构成字符串都是大 trie 上一条从祖先到后代的路径。
对这棵打 trie 建广义后缀自动机（其实应该叫多串）。
注意到转移图的前驱结点就是 trie 上的父亲对应的结点，直接接上去就好。
不同串之间可能因为所在的 trie 不同却同时有相同的前驱，这会使得重复计算，因为前一棵 trie 的后面的串显然与当前 trie 的字符串不共享。我们显式的建出的转移图其实是有问题的，但因为我们求的这个自动机能识别的字符串个数，所以我们只关心 parent 树的结构，而这个显然是一直正确的，即便是隐式的。所以不必多做处理，每次都对当前 trie 结点都新开一个自动机结点即可。
Code
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, sigma = 15;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v){e[ec] = (E){v, h[u]}; h[u] = ec++;}
struct N{int ch[sigma], f, len, cnt, n;} pool[maxn * sigma * sigma];
int h2[maxn], head = 1, pc = 2;
int add(int p, int c)
{
int newnode = pc++;
pool[newnode].n = h2[pool[newnode].len = pool[p].len + 1]; h2[pool[newnode].len] = newnode;
pool[newnode].cnt = 0;
for(; p && !pool[p].ch[c]; p = pool[p].f) pool[p].ch[c] = newnode;
if(!p) pool[newnode].f = head;
else if(pool[p].len + 1 == pool[pool[p].ch[c]].len) pool[newnode].f = pool[p].ch[c];
else
{
int q = pool[p].ch[c], r = pc++;
pool[r] = pool[q];
pool[r].n = h2[pool[r].len = pool[p].len + 1]; h2[pool[r].len] = r;
pool[q].f = pool[newnode].f = r;
for(; p && pool[p].ch[c] == q; p = pool[p].f) pool[p].ch[c] = r;
}
return newnode;
}
int col[maxn];
void dfs(int s, int u, int f = 0)
{
int t = add(s, col[u]);
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
dfs(t, v, u);
}
int deg[maxn];
int main()
{
int n, c; read(n, c);
for(int i = 1; i <= n; ++i) read(col[i]);
for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v), add_edge(v, u), ++deg[u], ++deg[v];
for(int i = 1; i <= n; ++i) if(deg[i] == 1) dfs(head, i);
long long ans = 0;
for(int i = n; i; --i) for(int j = h2[i]; j; j = pool[j].n)
ans += pool[j].len - pool[pool[j].f].len;
printf("%lld\n", ans);
return 0;
}