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)$