题意
学习了广义后缀自动机。
广义后缀自动机与普通后缀自动机的区别在于它是对多个串建的,于是可以处理多个串。
广义后缀自动机和普通后缀自动机的区别在于两个特判,可以见这篇题解
对于这题,因为叶子数量小于20,以每个叶子为根跑dfs,将跑到的字符串插入SAM即可,求不同子串个数是SAM的常规操作,见我的笔记。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2000010;
const int maxc=15;
int n,C,cnt;
int head[maxn],a[maxn],in[maxn];
struct edge{int to,nxt;}e[maxn<<1];
struct SAM
{
int tot,last;
int fa[maxn<<1],len[maxn<<1];
int ch[maxn<<1][maxc];
SAM(){last=tot=1;}
inline void add(int c)
{
if(ch[last][c]&&len[ch[last][c]]==len[last]+1){last=ch[last][c];return;}
int now=++tot;len[now]=len[last]+1;
int p=last;
while(p&&!ch[p][c])ch[p][c]=now,p=fa[p];
if(!p){fa[now]=1;last=now;return;}
int q=ch[p][c];
bool flag=0;
if(len[q]==len[p]+1)fa[now]=q;
else
{
if(p==last)flag=1;
int nowq=++tot;len[nowq]=len[p]+1;
for(int i=0;i<C;i++)ch[nowq][i]=ch[q][i];
fa[nowq]=fa[q],fa[q]=fa[now]=nowq;
while(p&&ch[p][c]==q)ch[p][c]=nowq,p=fa[p];
if(flag)last=nowq;
}
if(!flag)last=now;
}
inline ll query()
{
ll res=0;
for(int i=2;i<=tot;i++)res+=len[i]-len[fa[i]];
return res;
}
}sam;
inline void add(int u,int v)
{
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
in[v]++;
}
void dfs(int x,int fa)
{
sam.add(a[x]);int last=sam.last;
for(int i=head[x];i;i=e[i].nxt)
{
int y=e[i].to;
if(y==fa)continue;
sam.last=last;dfs(y,x);
}
}
int main()
{
scanf("%d%d",&n,&C);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int u,v;scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
for(int i=1;i<=n;i++)if(in[i]==1)sam.last=1,dfs(i,0);
//cerr<<sam.tot<<endl;
printf("%lld",sam.query());
return 0;
}