DMPG '15 G3 - Kinako Bread 2

View as PDF
Submit solution
Points: 30 (partial)
Time limit: 1.8s
Memory limit: 256M
Author:
FatalEagle
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, N pieces in total, arranged on vertices of an undirected graph without cycles — a tree. The vertices in the tree are numbered from 1 to N. 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 R_k and R_c loaves, respectively. However, the bread is so tasty that she would like to eat at least L_k and L_c loaves of it, respectively (0 \le L_i \le R_i \le N). 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 N, L_k, R_k, L_c, R_c.
The second line of input will have a string representing the type of bread on each vertex from 1 to N. The i^\text{th} character will be K if the type of bread on vertex i is kinako bread or C if it's a croissant.
The next N-1 lines will contain the edges of the tree, in the format u\ v. That means there is an edge between vertex u and vertex v.

Constraints

Subtask 1 [30%]

2 \le N \le 1\,000

Subtask 2 [30%]

2 \le N \le 200\,000
L_c = R_c = 0
All of the bread will be kinako bread.

Subtask 3 [40%]

2 \le N \le 200\,000

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

Comments