记录编号	358715	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015]诸神眷顾的幻想乡	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.113 s
提交时间	2016-12-18 14:52:50	内存使用	97.18 MiB

#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e6+10,M=2e5+10;
int n,c,w[M],v[M],head[M],tail[M],next[M],du[M],cnt;
void add(int f,int t){
	w[++cnt]=t;
	if (!head[f]) head[f]=tail[f]=cnt;
		else tail[f]=next[tail[f]]=cnt;
}
int go[N][10],len[N],par[N],root,top;
int New(int L){len[++top]=L;return top;}
int extend(int last,int w){
	int p=last,np=New(len[p]+1);
	while (p&&!go[p][w]) go[p][w]=np,p=par[p];
	if (!p) par[np]=root;
	else{
		int q=go[p][w];
		if (len[p]+1==len[q]) par[np]=q;
		else{
			int nq=New(len[p]+1);
			memcpy(go[nq],go[q],sizeof go[q]);
			par[nq]=par[q];
			par[np]=par[q]=nq;
			while (p&&go[p][w]==q) go[p][w]=nq,p=par[p];
		}
	}
	return np;
}
int vis[M];
void dfs(int x,int now,int C){
	int last=extend(now,v[x]);
	vis[x]=C;
	for (int i=head[x];i;i=next[i])
	if (vis[w[i]]!=C) dfs(w[i],last,C);
}
int main()
{
	freopen("zjoi15_substring.in","r",stdin);
	freopen("zjoi15_substring.out","w",stdout);
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;i++) scanf("%d",&v[i]);
	for (int i=1;i<n;i++){
		int f,t;
		scanf("%d%d",&f,&t);
		du[f]++;du[t]++;
		add(f,t);add(t,f);
	}
	root=New(0);
	for (int i=1;i<=n;i++)
	if (du[i]<=1) dfs(i,root,i);
	long long ans=0;
	for (int i=1;i<=top;i++)
		ans+=len[i]-len[par[i]];
	printf("%lld\n",ans);
	return 0;
}