记录编号	161053	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015]诸神眷顾的幻想乡	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.937 s
提交时间	2015-04-30 21:47:41	内存使用	113.01 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100003, maxs = 1000000;
typedef long long LL;
int N, c, *adj[maxn], d[maxn], col[maxn], leaf[22], lcnt;

struct SAM{
	SAM *son[10], *link;
	int len;
	LL cnt;
}Node[maxs<<1], *iter = Node + 1;

inline SAM * insert(SAM *last, int ch){
	SAM *cur = iter++, *it, *s, *clone;
	cur->len = last->len + 1;
	it = last;
	while(it && !it->son[ch])it->son[ch] = cur, it = it->link;
	if(!it)cur->link = Node;
	else{
		if(it->len + 1 == (s = it->son[ch])->len)cur->link = s;
		else{
			clone = iter++;*clone = *s;clone->len = it->len + 1;
			cur->link = s->link = clone;
			do{
				it->son[ch] = clone;
				it = it->link;
			}while(it && it->son[ch] == s);
		}
	}
	return cur;
}

void Build(SAM *last, int cur, int p){
	SAM *tmp = insert(last, col[cur]);
	int son;
	for(int i = 0;i < d[cur];++i)if((son = adj[cur][i]) != p)
		Build(tmp, adj[cur][i], cur);
}

inline void init(){
	getd(N), getd(c);
	size_t intsize = sizeof(int);
	int i, a, b, u[maxn], v[maxn], it[maxn] = {0};
	for(i = 1;i <= N;++i)getd(col[i]);
	for(i = 1;i < N;++i){
		getd(u[i]), getd(v[i]);
		++d[u[i]], ++d[v[i]];
	}
	for(i = 1;i <= N;++i){
		adj[i] = (int*)malloc(intsize * (d[i] + 1));
		if(d[i] == 1)leaf[lcnt++] = i;
	}
	for(i = 1;i < N;++i){
		a = u[i], b = v[i];
		adj[a][it[a]++] = b;
		adj[b][it[b]++] = a;
	}
	for(i = 0;i < lcnt;++i)Build(Node, leaf[i], 0);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(zjoi15_substring);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	init();
	LL Ans = 0;
	for(SAM *it = Node + 1;it != iter;++it)Ans += it->len - it->link->len;
	printf("%lld\n", Ans);

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}