DMPG '15 G3 - Kinako Bread 2

View as PDF

Points: 30 (partial)
Time limit: 4.0s
Memory limit: 256M

Author:
Problem types

Tohka's favorite food is kinako bread, but she likes croissants too. For dinner, Shido has bought Tohka some kinako bread and some croissants to eat, pieces in total, arranged on vertices of an undirected graph without cycles — a tree). The vertices in the tree are numbered from to . Tohka is very touched that Shido would buy her so much bread, but she is on a diet. For each of kinako bread and croissants, Tohka doesn't want to eat more than and loaves, respectively. However, the bread is so tasty that she would like to eat at least and loaves of it, respectively . Tohka has decided that she will eat all the bread on the vertices in a path between two vertices of the tree, and no more. How many ways can she choose a path of the tree to eat?

Note: A path is a sequence of unique vertices such that each pair of adjacent vertices in the path are connected by an edge in the tree. Specifically, a sequence of one vertex is considered a path.

Input Specification

The first line of input will have , , , , .
The second line of input will have a string representing the type of bread on each vertex from to . The character will be K if the type of bread on vertex is kinako bread or C if it's a croissant.
The next lines will contain the edges of the tree, in the format . That means there is an edge between vertex and vertex .

Output Specification

The output should consist of one integer on a single line, the number of ways Tohka can pick a path of the tree to eat.

Sample Input

10 1 2 0 2
KCCKCKKCKK
1 2
1 3
2 4
1 5
3 6
3 7
6 8
5 9
5 10

Sample Output

38