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

**only**when stuck, and

**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.

**Submitting an official solution before solving the problem yourself is a bannable offence.**

Author:

#### Solution Sketch

##### Subtask 1

We can go through all subsets of vertices using a bitmask technique and count the number of subsets that have exactly vertices, and at least red and black vertices, and forms a single connected component, using breadth first search, depth first search, of the union find data structure.

**Time Complexity:**

##### Subtask 2

For the second subtask, we can go through all triples of edges and check if it the edges form a single connected component. If it does, then there must be exactly vertices in the connected component. From here, we can check it there are red and black vertices.

**Time Complexity:**

##### Subtask 3

For the third subtask, we will do dynamic programming on a tree. First, we will arbitrarily root the tree at a vertex. For each vertex, we will have be the number of subgraphs that are in the subtree of vertex , that include vertex , with size , red vertices, and black vertices. A quick time and memory optimization is that we only need to keep track of . For each vertex, we can go through each of its children and merge the dp arrays. Let be a child of . To merge the arrays and , for all tuples , we will add the product of and to . Remember to mod correctly. The final answer will be the sum of for all vertices .

**Time Complexity:**

## Comments