题目链接：F-ABCBA
题意：给出一颗树，树上节点为一个字母，q次询问，每次询问u，v，从v到u的链上组成的字符串，包含序列"ABCBA"的个数（不是子串，可以不连续）。
给要求的这个序列编号:1,2,3,4,5；
首先树剖两次dfs预处理。
定义 a [ i ] [ j ] a[i][j] a[i][j]表示当前串包含序列 [ i , j ] [i,j] [i,j]的数量。
用线段树来维护，正着合并以及反着合并，因为树剖查询的时候，需要两条链跳跃。

struct Node{ int a[6][6]; }tree[maxn<<2|1][2],ansu,ansv; const int mod=10007; Node marge(Node a,Node b){ Node ans; for(int i=1; i<=5; ++i) for(int j=i; j<=5; ++j) ans.a[i][j]=a.a[i][j]+b.a[i][j],ans.a[i][j]%=mod; for(int i=1; i<=5; ++i) for(int j=i; j<=5; ++j) for(int k=j+1; k<=5; ++k) ans.a[i][k]=(ans.a[i][k]+a.a[i][j]*b.a[j+1][k])%mod; return ans; }void build(int l,int r,int k){ if(l==r){ if(val[l]=='A'){ tree[k][1].a[1][1]=tree[k][1].a[5][5]=1; } else if(val[l]=='B'){ tree[k][1].a[2][2]=tree[k][1].a[4][4]=1; } else if(val[l]=='C'){ tree[k][1].a[3][3]=1; } tree[k][0]=tree[k][1]; return ; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); tree[k][0]=marge(tree[k<<1][0],tree[k<<1|1][0]); tree[k][1]=marge(tree[k<<1|1][1],tree[k<<1][1]); }

#include using namespace std; const int maxn=3e4+7; struct Edge{ int v,next; }edge[maxn<<1]; int head[maxn],top; void add(int u,int v){ edge[top].v=v; edge[top].next=head[u]; head[u]=top++; }void init(){ memset(head,-1,sizeof(head)); top=0; }int fa[maxn],dfn[maxn],num,topp[maxn],son[maxn],siz[maxn],dep[maxn]; char val[maxn]; char s[maxn]; bool vis[maxn]; void dfs1(int u){ int v; vis[u]=1; siz[u]=1; int maxx=-1; for(int i=head[u]; i!=-1; i=edge[i].next){ v=edge[i].v; if(vis[v]) continue; dep[v]=dep[u]+1; fa[v]=u; dfs1(v); siz[u]+=siz[v]; if(siz[v]>maxx){ son[u]=v; maxx=siz[v]; } } }void dfs2(int u,int last){ dfn[u]=++num; val[num]=s[u]; topp[u]=last; if(!son[u]) return ; dfs2(son[u],last); for(int i=head[u]; i!=-1; i=edge[i].next){ int v=edge[i].v; if(dfn[v]||v==son[u]) continue; dfs2(v,v); } }struct Node{ int a[6][6]; }tree[maxn<<2|1][2],ansu,ansv; const int mod=10007; Node marge(Node a,Node b){ Node ans; for(int i=1; i<=5; ++i) for(int j=i; j<=5; ++j) ans.a[i][j]=a.a[i][j]+b.a[i][j],ans.a[i][j]%=mod; for(int i=1; i<=5; ++i) for(int j=i; j<=5; ++j) for(int k=j+1; k<=5; ++k) ans.a[i][k]=(ans.a[i][k]+a.a[i][j]*b.a[j+1][k])%mod; return ans; }void build(int l,int r,int k){ if(l==r){ if(val[l]=='A'){ tree[k][1].a[1][1]=tree[k][1].a[5][5]=1; } else if(val[l]=='B'){ tree[k][1].a[2][2]=tree[k][1].a[4][4]=1; } else if(val[l]=='C'){ tree[k][1].a[3][3]=1; } tree[k][0]=tree[k][1]; return ; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); tree[k][0]=marge(tree[k<<1][0],tree[k<<1|1][0]); tree[k][1]=marge(tree[k<<1|1][1],tree[k<<1][1]); }Node query0(int l,int r,int k,int L,int R){ if(l>=L&&r<=R) return tree[k][0]; int mid=(l+r)>>1; if(R<=mid) return query0(l,mid,k<<1,L,R); else if(L>mid) return query0(mid+1,r,k<<1|1,L,R); return marge(query0(l,mid,k<<1,L,R),query0(mid+1,r,k<<1|1,L,R)); }Node query1(int l,int r,int k,int L,int R){ if(l>=L&&r<=R) return tree[k][1]; int mid=(l+r)>>1; if(R<=mid) return query1(l,mid,k<<1,L,R); else if(L>mid) return query1(mid+1,r,k<<1|1,L,R); return marge(query1(mid+1,r,k<<1|1,L,R),query1(l,mid,k<<1,L,R)); } int n; int myfindchain(int x,int y){ memset(ansu.a,0,sizeof(ansu.a)); memset(ansv.a,0,sizeof(ansv.a)); while(topp[x]!=topp[y]){ if(dep[topp[x]]>dep[topp[y]]){//x爬向y; ansu=marge(ansu,query1(1,n,1,dfn[topp[x]],dfn[x])); x=fa[topp[x]]; } else{//y爬向x; ansv=marge(query0(1,n,1,dfn[topp[y]],dfn[y]),ansv); y=fa[topp[y]]; } } if(dep[x]>dep[y]){ return marge(marge(ansu,query1(1,n,1,dfn[y],dfn[x])),ansv).a[1][5]; } else{ return marge(ansu,marge(query0(1,n,1,dfn[x],dfn[y]),ansv)).a[1][5]; } }int main(){ dep[1]=1; init(); int u,v,q; scanf("%d%d",&n,&q); scanf("%s",s+1); for(int i=1; i