首页 > 试题广场 >

ABCBA

[编程题]ABCBA
给出一颗n个结点n-1条边的树，再给出一个长度为n的字符串s，树上的每个点都表示一个字符，点i表示的字符是s[i]，其只包含大写拉丁字符。再给出q个查询，对于每个查询，会给出两个整数u,v,表示树上的两个点。对于每个查询你将从点v开始走最短路径走到点u，并按行走的顺序连接每个结点上的字符，形成一个新的字符串H,你需要计算字符串H中包含子串‘ABCBA’的个数。子串的定义就是存在任意下标a<b<c<d<e，那么”s[a]s[b]s[c]s[d]s[e]”就构成s的一个子串。如”ABC”的子串有”A”、”B”、”C”、”AB”、”AC”、”BC”、”ABC”。

输入描述:
第一行两个数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的个数为1

对于查询1 8，从结点8走到结点3，形成的字符串为AABCBABA，子串ABCBA的个数为6
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 5浏览

热门推荐

相关试题

ABCBA

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号