神奇的性质，叶子节点不超过20个。
然后把这些节点提出来构成一颗新树，那么这些树恰好包含了所有的情况。
所以直接广义后缀自动机。
然后统计本质不同的字符串就很简单显然了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define ll long long
#define maxn 4000005 struct Generalized_Suffix_Array{
int cnt;
int go[maxn][10],l[maxn],fa[maxn];
int add(int x,int p)
{
// printf("Add %d on %d\n",x,p);
int q;
if (q=go[p][x])
{
if (l[p]+1==l[q]) return q;
else
{
int nq=++cnt;l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof go[q]);
fa[nq]=fa[q];
fa[q]=nq;
for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
return nq;
}
}
else
{
int np=++cnt; l[np]=l[p]+1;
for (;p&&!go[p][x];p=fa[p]) go[p][x]=np;
if (!p) fa[np]=1;
else
{
q=go[p][x];
if (l[q]==l[p]+1) fa[np]=q;
else
{
int nq=++cnt;
l[nq]=l[p]+1;
memcpy(go[nq],go[q],sizeof go[q]);
fa[nq]=fa[q];
fa[q]=fa[np]=nq;
for (;p&&go[p][x]==q;p=fa[p]) go[p][x]=nq;
}
}
return np;
}
}
void init()
{cnt=1;memset(go,0,sizeof go);}
void solve()
{
ll ans=0;
F(i,1,cnt)
{
// printf("%d --> %d\n",i,fa[i]);
// printf("%d %d\n",l[i],l[fa[i]]);
ans+=l[i]-l[fa[i]];
}
printf("%lld\n",ans);
}
}sam; int h[maxn],to[maxn],ne[maxn],en=0,du[maxn]; void addedge(int a,int b)
{to[en]=b;ne[en]=h[a];h[a]=en++;du[a]++;} int n,c,a[maxn]; void dfs(int o,int fa,int p)
{
// printf("dfs on %d %d %d\n",o,fa,p);
int np=sam.add(a[o],p);
for (int i=h[o];i>=0;i=ne[i]) if (to[i]!=fa) dfs(to[i],o,np);
} int main()
{
sam.init();
scanf("%d%d",&n,&c);
memset(h,-1,sizeof h);
F(i,1,n) scanf("%d",&a[i]);
F(i,1,n-1)
{
int a,b;
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
F(i,1,n) if (du[i]==1) dfs(i,-1,1);
sam.solve();
}