import java.util.Scanner;
public class Main {
public static void main(String[] arg) {
Scanner scanner = new Scanner(System.in);
// todo
}
}
NC25146. ABCBA
描述
输入描述
第一行两个数n，q。1<=n<=3e4,1<=q<=1e5。
第二行一个长度为n的字符串s。所有字符都为大写拉丁字符。
接下来n-1行每行两个数u,v表示点u和点v之间有一条边
接下来q行每行两个整数u,v。1<=u,v<=n。
输出描述
对于每个查询输出一个整数表示点v到点u的路径上”ABCBA”子串的个数，每个答案占一行，答案对10007取模。
示例1
输入:
8 3 ABABCBAA 1 2 2 3 3 4 4 5 5 6 6 7 7 8 3 7 2 3 1 8
输出:
1 0 6
说明:
对于查询3 7，从结点7走到结点3，形成的字符串为ABCBA，子串ABCBA的个数为1C++11(clang++ 3.9) 解法, 执行用时: 2340ms, 内存消耗: 20064K, 提交时间: 2019-12-08 19:54:49
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=3e4+5,mod=10007;struct node{short a[6][6];node(){memset(a,0,sizeof(a));}}t[N<<2][2];char s[N];int n,q,head[N],si[N],id,f[N],rev[N],dep[N],son[N],fa[N],top[N],nex[N<<1],to[N<<1];int tot=1;void add(int u,int v){to[++tot]=v;nex[tot]=head[u];head[u]=tot;}node ans;node Merge(node a,node b){register int i,j,k;for(i=1;i<=5;i++)for(j=i;j<=5;j++)ans.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;for(i=1;i<=5;i++)for(j=1;j<=5;j++)for(k=j+1;k<=5;k++)ans.a[i][k]=(ans.a[i][k]+(int)a.a[i][j]*b.a[j+1][k])%mod;return ans;}void build(int l,int r,int k){if(l==r){if(s[rev[l]]=='A')t[k][0].a[1][1]=t[k][0].a[5][5]=1;if(s[rev[l]]=='B')t[k][0].a[2][2]=t[k][0].a[4][4]=1;if(s[rev[l]]=='C')t[k][0].a[3][3]=1;t[k][1]=t[k][0];return;}int m=l+r>>1;build(l,m,k<<1);build(m+1,r,k<<1|1);t[k][0]=Merge(t[k<<1][0],t[k<<1|1][0]);t[k][1]=Merge(t[k<<1|1][1],t[k<<1][1]);}node query(int l,int r,int k,int x,int y,int opt){if(r<x||l>y) return node();if(l>=x&&r<=y) return t[k][opt];int m=l+r>>1;return opt?Merge(query(m+1,r,k<<1|1,x,y,opt),query(l,m,k<<1,x,y,opt)):Merge(query(l,m,k<<1,x,y,opt),query(m+1,r,k<<1|1,x,y,opt));}void dfs1(int u,int p){si[u]=1;fa[u]=p;dep[u]=dep[p]+1;for(int i=head[u];i;i=nex[i]){int v=to[i];if(v==p) continue;dfs1(v,u);si[u]+=si[v];if(si[v]>si[son[u]]) son[u]=v;}}void dfs2(int u){f[u]=++id;rev[id]=u;if(son[u]) top[son[u]]=top[u],dfs2(son[u]);for(int i=head[u];i;i=nex[i]){int v=to[i];if(v==fa[u]||v==son[u]) continue;top[v]=v;dfs2(v);}}int Q(int u,int v){node ansu,ansv;while(top[u]!=top[v]){if(dep[top[u]]>dep[top[v]]) ansu=Merge(query(1,n,1,f[top[u]],f[u],0),ansu),u=fa[top[u]];else ansv=Merge(ansv,query(1,n,1,f[top[v]],f[v],1)),v=fa[top[v]];}if(dep[u]>dep[v]) return Merge(Merge(ansv,query(1,n,1,f[v],f[u],0)),ansu).a[1][5];else return Merge(Merge(ansv,query(1,n,1,f[u],f[v],1)),ansu).a[1][5];}int main(){scanf("%d%d",&n,&q);scanf("%s",s+1);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs1(1,0);top[1]=1;dfs2(1);build(1,n,1);while(q--){int u,v;scanf("%d%d",&u,&v);printf("%d\n",Q(u,v));}}