|
||||||||||
Just A ChallengeTime Limit: 20000/10000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 167 Accepted Submission(s): 12 Problem Description Matt receives a gift from his friend Bobo. It is a tree which has N vertices and (N - 1) edges with single character. Yes, it is the tree in computer science. Matt denotes the number of edges between vertices a and b as d(a, b). The string obtained by concatenating all characters from a to b is defined as s(a, b). Given string L and R of length M, Matt would like to know the number of (a, b) s.t. ¡ñ d(a, b) = M, ¡ñ L<=s(a, b)<=R. where "<=" means lexicographical comparision. Input The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow. For each test case, the first line contains two integers N (2<=N<=10^5) and M (1<=M<N). Each of the following (N - 1) lines contains ai, bi, ci denoting an edge between vertex ai and bi with character ci (1<=ai, bi<=n).The vertices are conveniently labled with 1, 2,¡¡, n. ci is either 'a' or 'b'. The last two lines contain string L and R (|L| = |R| = M, L<=R). L and R consist of 'a' and 'b'. Output For each test case, output one line "Case #x: y", where x is the case number (starting from 1), y is the number of (a, b). Sample Input
Sample Output
Hint Please use #pragma comment(linker, "/STACK:16777216") Source | ||||||||||
|