F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Just A Challenge

Time 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
2 2 1 1 2 a a b 4 2 1 2 a 2 3 b 3 4 a aa ab
 

Sample Output
Case #1: 2 Case #2: 2
 

Hint
Please use #pragma comment(linker, "/STACK:16777216")
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 21:08:15, Gzip enabled