## Wesley's Anger Contest 1 Problem 4 (Hard Version) - A Red-Black Tree Problem

View as PDF

Points: 17
Time limit: 0.6s
Memory limit: 512M

Author:
Problem types

It is well known that Wesley is bad at dynamic programming. Six months after the contest, Wesley learned that you can solve the original problem with a significantly better time complexity. He decided to create a new problem with tighter constraints. The only differences between this problem and the original are the bounds on and , as well as the time and memory limits. In addition, there will not be language specific time limits.

You are given a tree with vertices. Recall that a tree is a connected graph where there is exactly one path between any two vertices. Each vertex in this tree is assigned a colour, red or black. You are asked to determine the number of balanced subgraphs with exactly vertices. A subgraph is considered to be balanced if all vertices are connected and there are at least red vertices and black vertices.

Wesley originally wanted you to output the full answer, but he decided to be nice and only ask you to output it modulo . It may be helpful to know that is prime and .

For this question, a connected subgraph is a subset of the original vertices and edges that form a tree.

#### Constraints

The graph is a tree.

#### Input Specification

The first line contains 2 integers, and .

The next line contains a string of characters, describing the colouring of the tree. Each character is either R or B. If the character is R, then vertex is red. Otherwise, it is black.

The next lines describe the edges of the tree. Each line contains 2 integers, , , indicating an edge between and .

#### Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output a single integer, the number of balanced subgraphs with exactly vertices, modulo .

#### Sample Input 1

6 5
BBBRBR
1 2
2 3
2 4
3 5
2 6

#### Sample Output 1

2

#### Sample Explanation 1

The two balanced subgraphs of size are and .

#### Sample Input 2

5 4
RBRBR
1 2
2 3
2 4
2 5

#### Sample Output 2

3

#### Sample Explanation 2

The three balanced subgraphs of size are , , and .