记录编号	252129	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[ZJOI 2015]诸神眷顾的幻想乡	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	2.248 s
提交时间	2016-04-19 15:39:14	内存使用	90.17 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

int n,C,cnt=1,ls=1,rt=1;
long long pr;
struct hzzdj
{
	struct u
	{
		int pre;
		int d;
		int e[10];
		void clear()
		{
			memset(e,0,sizeof(e));
			pre=d=0;
		}
	}c[2000010];

	void gj(int a)
	{
		int p=c[ls].e[a],k=ls;
		if(p)
		{
			if(c[p].d==c[k].d+1)
			{
				ls=p;
				return;
			}
			int np=++cnt;
			c[np].clear();
			c[np].d=c[k].d+1;
			memcpy(c[np].e,c[p].e,sizeof(c[np].e));
			c[np].pre=c[p].pre;
			while(k&&c[k].e[a]==p)
			{
				c[k].e[a]=np;
				k=c[k].pre;
			}
			c[p].pre=np;
			//pr+=c[np].d-c[c[np].pre].d;
			ls=np;
			return;
		}
		p=++cnt;
		c[p].clear();
		c[p].d=c[k].d+1;
		while(k&&!c[k].e[a])
		{
			c[k].e[a]=p;
		    k=c[k].pre;
		}
		if(!k)
		    c[p].pre=rt;
		else
		{
			int q=c[k].e[a];
			if(c[q].d==c[k].d+1)
			{
				c[p].pre=q;
			}
			else
			{
				int nq=++cnt;
				c[nq].clear();
				c[nq].d=c[k].d+1;
				memcpy(c[nq].e,c[q].e,sizeof(c[nq].e));
				c[nq].pre=c[q].pre;
				while(k&&c[k].e[a]==q)
				{
					c[k].e[a]=nq;
					k=c[k].pre;
				}
				c[p].pre=c[q].pre=nq;
			}
		}
		pr+=c[p].d-c[c[p].pre].d;
		ls=p;
	}
}A;
struct uu
{
	int b;
	int x;
}c[200010];
int h[100010],l,w[100010];
int r[100010],st[100010],tp;

inline void gj(int a,int b)
{
	c[++l].b=b;
	c[l].x=h[a];
	h[a]=l;
}

void g(int a,int fa)
{
	st[++tp]=w[a];
	//if(a==1&&fa==0)
	//    printf("W%d\n",w[1]);
	bool b=1;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(u==fa)
		    continue;
		b=0;
		g(u,a);
	}
	if(b)
	{
		/*for(int i=1;i<=tp;i++)
		    printf("%d ",st[i]);
		puts("");*/
		ls=rt;
		for(int i=1;i<=tp;i++)
			A.gj(st[i]);
		//printf("%d\n",pr);
	}
	--tp;
}

int main()
{
	int __size__ = 30 << 20;
	char *__p__ = (char*)malloc(__size__) + __size__;
	__asm__("movl %0, %%esp\n" :: "r"(__p__));
	freopen("zjoi15_substring.in","r",stdin);
	freopen("zjoi15_substring.out","w",stdout);
	//for(int i=1;i<=1000000;i++)
	//   A.c[i].clear();
	scanf("%d%d",&n,&C);
	for(int i=1;i<=n;i++)
	    scanf("%d",&w[i]);
	  //  printf("%d\n",w[1]);
	for(int i=1;i<n;++i)
	{
		int aa,bb;
		scanf("%d%d",&aa,&bb);
		gj(aa,bb);
		gj(bb,aa);
		r[aa]++;
		r[bb]++;
	}
	rt=ls=1;
	for(int i=1;i<=n;i++)
	if(r[i]==1)
	{
		//printf("%d-----------------------\n",i);
		//if(tp!=0)
		//    puts("Sxbk");
		g(i,0);
	}
	printf("%lld",pr);
	//while(1);
	getchar();
	getchar();
}