Editorial for Wesley's Anger Contest 1 Problem 4 (Easy Version) - A Red-Black Tree Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 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 that 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