题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3926
广义后缀自动机...
久仰公之大名啊...
太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过$20$个。
这就是说叶子节点的个数不超过$20$个，我们知道树上的每一条路径一定对应了一个:以某一个叶子节点为根的tire树的后缀的前缀(也就是子串),我们知道SAM是可以统计不同子串的个数的即：${\sum _{i=1}^{n} (len[i]-len[fa[i]])}$
考虑如何把这20棵tire构成一个后缀自动机，我们在只有一个串的时候$np$就是直接指向前一个字符的位置，因为我们现在是树结构，所以$np$指向的应该是该点在$trie$树中父节点的位置，其他的就和普通的$SAM$一样，为了找到节点的父亲，$DFS$找即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 1000010
#define llg long long
#define SIZE 11
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,m,last=,root=,du[maxn],v[maxn]; vector<llg>a[maxn]; struct SAM
{
struct
{
llg len,f,ch[SIZE];
void init(){len=,f=,memset(ch,,sizeof(ch));}
}e[maxn*]; llg insert(llg p,llg c)
{
llg np=++last; e[np].init();
e[np].len=e[p].len+;
for (;p && !e[p].ch[c];p=e[p].f) e[p].ch[c]=np;
if (!p) e[np].f=root;
else
{
llg q=e[p].ch[c];
if (e[q].len==e[p].len+) e[np].f=q;
else
{
llg nq=++last;
e[nq].init();
e[nq]=e[q];
e[nq].len=e[p].len+;
e[q].f=e[np].f=nq;
for (;p && e[p].ch[c]==q;p=e[p].f) e[p].ch[c]=nq;
}
}
return np;
}
}sam; void init()
{
llg x,y;
cin>>n>>m;
for (llg i=;i<=n;i++) scanf("%lld",&v[i]);
for (llg i=;i<n;i++)
{
scanf("%lld%lld",&x,&y);
a[x].push_back(y),a[y].push_back(x);
du[x]++,du[y]++;
}
} void dfs(llg x,llg fa,llg p)
{
llg t=sam.insert(p,v[x]),w=a[x].size();
for (llg i=;i<w;i++)
if (a[x][i]!=fa)
dfs(a[x][i],x,t);
} int main()
{
yyj("god");
init();
for (llg i=;i<=n;i++) if (du[i]==) dfs(i,,);
llg ans=;
for (llg i=;i<=last;i++) ans+=sam.e[i].len-sam.e[sam.e[i].f].len;
cout<<ans;
return ;
}