1633 - Tree
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 53
Solved: 9
- Description
- LAZ has a tree of N nodes numbered from 1 to N, each node i contains a lowercase letter c(i). Let(a, b) represent a path from node a to node b,
then we can get a string S(a,b) consisting of letters along the shortest path. For example, if (a1, a4) = a1‐>a2‐>a3‐>a4, then the string we get is S(a1,a4) =c(a1)c(a2)c(a3)c(a4).
We define the value of (a, b) as F(S(a,b)), the length of (a, b) as L(a,b) which equals the number of edges in the path , and the ith node appearing in the path as
P(a,b,i), (i = 0,1, …, L(a,b)), then:
Now please count how many (a, b) in the given tree satisfies L(a,b) = X, F(S(a,b)) = Y. - Input
- The first line contains a single integer T indicating the number of test cases.
In each of the following T test cases:
The first line contains three integers N, X, Y. (0<N<=50000, 0<=X, Y<2*10^9)
The second line contains N lowercase letters c(1), c(2), …, c(N).
Then N – 1 lines follows, each line contains two integers ui, vi representing an edge between ui
and vi. - Output
- For each test case, output one line containing the number of (a, b) that satisfies L(a, b) = X,
F(S(a,b)) = Y. - sample input
-
1 4 2 33853 a a a a 1 2 1 3 1 4
- sample output
-
6
- hint
- The 6 paths are (2,3) (2,4) (3,2) (3,4) (4,2) (4,3).
- source
- The 8th(2013) ACM Programming Contest of HUST