BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡

2017-02-20T22:27:00+08:00

##Description
幽香是全幻想乡里最受人欢迎的萌妹子，这天，是幽香的2600岁生日，无数幽香的粉丝到了幽香家门前的太阳花田上来为幽香庆祝生日。 
粉丝们非常热情，自发组织表演了一系列节目给幽香看。幽香当然也非常高兴啦。 
这时幽香发现了一件非常有趣的事情，太阳花田有n块空地。在过去，幽香为了方便，在这n块空地之间修建了n-1条边将它们连通起来。也就是说，这n块空地形成了一个树的结构。 
有n个粉丝们来到了太阳花田上。为了表达对幽香生日的祝贺，他们选择了c中颜色的衣服，每种颜色恰好可以用一个0到c-1之间的整数来表示。并且每个人都站在一个空地上，每个空地上也只有一个人。这样整个太阳花田就花花绿绿了。幽香看到了，感觉也非常开心。 
粉丝们策划的一个节目是这样的，选中两个粉丝A和B（A和B可以相同），然后A所在的空地到B所在的空地的路径上的粉丝依次跳起来（包括端点），幽香就能看到一个长度为A到B之间路径上的所有粉丝的数目（包括A和B）的颜色序列。一开始大家打算让人一两个粉丝（注意：A,B和B,A是不同的，他们形成的序列刚好相反，比如红绿蓝和蓝绿红）都来一次，但是有人指出这样可能会出现一些一模一样的颜色序列，会导致审美疲劳。 
于是他们想要问题，在这个树上，一共有多少可能的不同的颜色序列（子串）幽香可以看到呢？ 
太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。

###Input
第一行两个正整数n,c。表示空地数量和颜色数量。 
第二行有n个0到c-1之间，由空格隔开的整数，依次表示第i块空地上的粉丝的衣服颜色。（这里我们按照节点标号从小到大的顺序依次给出每块空地上粉丝的衣服颜色）。 
接下来n-1行，每行两个正整数u,v，表示有一条连接空地u和空地v的边。

###Output
一行，输出一个整数，表示答案。

###Sample Input
7 3
0 2 1 2 1 0 0
1 2
3 4
3 5
4 6
5 7
2 5

###Sample Output
30

###HINT
对于所有数据，1<=n<=100000, 1<=c<=10。 
对于15%的数据，n<=2000。 
另有5%的数据，所有空地都至多与两个空地相邻。 
另有5%的数据，除一块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。 
另有5%的数据，除某两块空地与三个空地相邻外，其他空地都分别至多与两个空地相邻。

###Solution
考虑一条从u到v的路径上的字符串，如果在两端不断加节点，一定可以扩充成一条两个度数为1的节点间的路径上的子串。
那么显然有一种方法是把20个节点两两间的字符串建成广义SAM，然后直接统计，但是这样时间、内存都会超。
建广义SAM时，每次会把last设为初始节点，那么对于这道题，也可以类似优化。
把每个度数为1的节点作为根dfs，每次dfs时记下当前last，然后在处理完一棵子树后还原last。

###Code
```c++
#define _GLIBCXX_IOSTREAM
#include<bits/stdc++.h>

typedef long long ll;

#define N 2000010

struct node
{
	int ma,inc;ll cnt;
	node*link,*nxt[10];
}pool[N*2],*pm=pool+1,*start=pool;

namespace _A{node*lst,*cur,*p,*q,*sq;}
void add(int t)
{
	using namespace _A;
	cur=pm++;
	cur->ma=lst->ma+1;
	for(p=lst;p&&!p->nxt[t];p=p->link)p->nxt[t]=cur;
	if(!p){cur->link=start;goto naive;}
	q=p->nxt[t];
	if(p->ma+1==q->ma){cur->link=q;goto naive;}
	sq=pm++;
	sq->ma=p->ma+1;
	memcpy(sq->nxt,q->nxt,sizeof(q->nxt));
	for(;p&&p->nxt[t]==q;p=p->link)p->nxt[t]=sq;
	sq->link=q->link;
	q->link=sq;
	cur->link=sq;
	naive:lst=cur;
}

struct edge
{
	int to;edge*ne;
}_e[200000],*e=_e,*p[100001];

inline void add(int a,int b)
{
	*e=(edge){b,p[a]};p[a]=e++;
}

int c[100001],deg[100001];

void dfs(int x,int fa)
{
	add(c[x]);
	node*t=_A::lst;
	for(edge*i=p[x];i;i=i->ne)
		if(i->to^fa)
		{
			_A::lst=t;
			dfs(i->to,x);
		}
}

node*q[N*2];

int main()
{
	int n,x,y;
	scanf("%d%*d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",c+i);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		deg[x]++;
		deg[y]++;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)if(deg[i]==1)
		_A::lst=start,dfs(i,0);
	for(node*i=pool;i<pm;i++)
		for(int j=0;j<10;j++)if(i->nxt[j])i->nxt[j]->inc++;
	int qe=0;
	for(node*i=pool;i<pm;i++)
		if(!i->inc)i->inc=1e9,q[qe++]=i;
	for(int i=0;i<qe;i++)
		for(int j=0;j<10;j++)if(q[i]->nxt[j])if(!--q[i]->nxt[j]->inc)
			q[i]->nxt[j]->inc=1e9,q[qe++]=q[i]->nxt[j];
	for(int i=qe-1;~i;i--)
	{
		for(int j=0;j<10;j++)if(q[i]->nxt[j])q[i]->cnt+=q[i]->nxt[j]->cnt;
		q[i]->cnt++;
	}
	printf("%lld",start->cnt-1);
}
```

mcfx's blog - SAM

BZOJ 3926: [Zjoi2015]诸神眷顾的幻想乡