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

Remember to use this editorial 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.

Authors: wleung_bvg

#### Solution Sketch

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: 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: 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: 