Description：

给一棵点上有字符的树，保证叶子节点不超过 $20$ 个，问有多少种本质不同的子串。

$1\leqslant n\leqslant 10^5$

Solution：

既然叶子只有 $20$ 个，那就分别以每个叶子为根把这棵树插到广义后缀自动机中，具体做法是每次在父亲在自动机上的位置的基础上继续构造，最后输出 $\sum s[i].maxl-s[s[i].par].maxl$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,c;

#define MAXN 100010

#define MAXC 10

int col[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN * 2];

int edgenum = 0;

int lin[MAXN] = {0};

int ind[MAXN];

void add(int a,int b)

{

	++ind[a];++ind[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

struct node

{

	int tr[MAXC];

	int par,maxl;

}s[MAXN * 40];

int ptr = 1,root = 1,last = 1;

int newnode(int l){int k = ++ptr;s[k].maxl = l;return k;}

int extend(int k,int p)

{

	int np = newnode(s[p].maxl + 1);

	for(;p && s[p].tr[k] == 0;p = s[p].par)s[p].tr[k] = np;

	if(p == 0)s[np].par = root;

	else

	{

		int q = s[p].tr[k];

		if(s[p].maxl + 1 == s[q].maxl)s[np].par = q;

		else

		{

			int nq = newnode(s[p].maxl + 1);

			memcpy(s[nq].tr,s[q].tr,sizeof(s[q].tr));

			s[nq].par = s[q].par;

			s[q].par = s[np].par = nq;

			for(;p && s[p].tr[k] == q;p = s[p].par)s[p].tr[k] = nq;

		}

	}

	return np;

}

void dfs(int k,int f,int p)

{

	int np = extend(col[k],p);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != f)dfs(e[i].to,k,np);

	}

	return;

} 

int main()

{

	scanf("%d%d",&n,&c);

	for(int i = 1;i <= n;++i)scanf("%d",&col[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	for(int i = 1;i <= n;++i)if(ind[i] == 1)dfs(i,0,root);

	long long ans = 0;

	for(int i = 2;i <= ptr;++i)ans += s[i].maxl - s[s[i].par].maxl;

	cout << ans << endl;

	return 0;

}