Subtask 1

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

Time Complexity: ~\mathcal{O}(N 2^N)~

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 ~4~ vertices in the connected component. From here, we can check that there are ~2~ red and ~2~ black vertices.

Time Complexity: ~\mathcal{O}(N^3)~

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 ~dp[v][i][r][b]~ be the number of subgraphs that are in the subtree of vertex ~v~, that include vertex ~v~, with size ~i~, ~r~ red vertices, and ~b~ black vertices. A quick time and memory optimization is that we only need to keep track of ~r, b \le 2~. For each vertex, we can go through each of its children and merge the dp arrays. Let ~w~ be a child of ~v~. To merge the arrays ~dp[v]~ and ~dp[w]~, for all tuples ~(i, r_i, b_i, j, r_j, b_j)~, we will add the product of ~dp[v][i][r_i][b_i]~ and ~dp[w][j][r_j][b_j]~ to ~merged[i + j][\min(2, r_i + r_j)][\min(2, b_i + b_j)]~. Remember to mod correctly. The final answer will be the sum of ~dp[v][K][2][2]~ for all vertices ~v~ ~(1 \le v \le N)~.

Time Complexity: ~\mathcal{O}(N K^2)~