Wesley's Anger Contest 1 Problem 4 - A Red-Black Tree Problem

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.4s
Java 2.5s
Python 4.5s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

You are given a tree with N 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 K vertices. A subgraph is considered to be balanced if all vertices are connected and there are at least 2 red vertices and 2 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 998\,244\,353. It may be helpful to know that 998\,244\,353 is prime and 998\,244\,353 = 119 \times 2^{23} + 1.

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


For this question, Python users are recommended to use PYPY over CPython.

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

Subtask Points N, K
1 10\% 1 \le N \le 16
1 \le K \le N
2 15\% 1 \le N \le 100
1 \le K \le \min(4, N)
3 75\% 1 \le N \le 100
1 \le K \le N

For all subtasks:

1 \le u_i, v_i \le N

The graph is a tree.

Input Specification

The first line contains 2 integers, N and K.

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

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

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 K vertices, modulo 998\,244\,353.

Sample Input 1

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

Sample Output 1


Sample Explanation 1

The two balanced subgraphs of size 5 are \{1,2,3,4,6\} and \{2,3,4,5,6\}.

Sample Input 2

5 4
1 2
2 3
2 4
2 5

Sample Output 2


Sample Explanation 2

The three balanced subgraphs of size 4 are \{1,2,3,4\}, \{1,2,4,5\}, and \{2,3,4,5\}.


  • -5
    Plasmatic  commented on July 9, 2019, 12:29 a.m.

    This comment is hidden due to too much negative feedback. Click here to view it.