本文共 1159 字，大约阅读时间需要 3 分钟。

题目大意： 给出一棵树，每个点有颜色，任意选出两点从 $A$ 走到 $B$ 可以得到一个颜色序列，问有多少种不同的颜色序列。

题解

由于叶子节点很少，所以从每个叶子节点出发走到其他的叶子节点，把该路径形成的颜色序列插入到广义SAM中，然后统计有多少个不同的子串即可。

代码如下：

#include 
   
    #include 
    
     using namespace std;#define maxn 100010int n,m,a[maxn];struct edge{
   int y,next;};edge e[maxn<<1];int first[maxn],len=0;void buildroad(int x,int y){
   e[++len]=(edge){
   y,first[x]};first[x]=len;}int fa[maxn],du[maxn];struct state{
   int len,link,next[10];}st[maxn*40];int id=0,last,now,p,q;void extend(int x){
   	now=++id;	st[now].len=st[last].len+1;	for(p=last;p!=-1&&!st[p].next[x];p=st[p].link)st[p].next[x]=now;	if(p!=-1)	{
   		q=st[p].next[x];		if(st[p].len+1==st[q].len)st[now].link=q;		else		{
   			int clone=++id;			st[clone]=st[q];st[clone].len=st[p].len+1;			for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;			st[q].link=st[now].link=clone;		}	}	last=now;}void dfs(int x,bool S){
   	if(du[x]==1&&!S){
   last=0;for(int i=x;i;i=fa[i])extend(a[i]);}	else for(int i=first[x];i;i=e[i].next)	if(e[i].y!=fa[x])fa[e[i].y]=x,dfs(e[i].y,false);}long long ans=0;int main(){
   	scanf("%d %d",&n,&m);	for(int i=1;i<=n;i++)scanf("%d",&a[i]);	for(int i=1,x,y;i
    
   

转载地址：http://hjnib.baihongyu.com/