Solving this problem requires a deep understanding of how Subset Sum DP works. In fact, with a proper abstraction, you can almost convert it to a Subset-Sum DP problem.
In the subset-sum problem, we have a zero-indexed array of n elements. To simplify the mathematical notation, for each node x, define the node vertically below it as x*. If we capture each x and x* in a rectangular box, we will get an array of n blocks (let's say, zero-indexed), and we need to perform some operations on these blocks. This is the first level of abstraction which makes the numbers in subset sum DP analogous to blocks in this problem.
Next, to figure out the DP definition, recall that in subset-sum problem, even though we are supposed to find the number of subsets of the entire array with sum exactly equal to k, we define dp[i][j] as the number of subsets with sum equal to j for all j <= k. Why is this so? It's because j_1 + j_2 can become equal to k. In fact, for each DP problem, all states can be broadly classified into 3 categories,
- Directly useful
- Indirectly useful
- Hopeless
So, any subset with sum equal to k is directly useful, subsets with sum less than k are indirectly useful and subsets with sum greater than k are hopeless.
Recall that, in Knapsack problem, we also maintain another dimension of DP capturing the total weights we've already used so far. Since we need to delete some amount of edges from these blocks, let's define dp[i][j] as the number of ways to delete exactly j edges from blocks [0, ... i] such that the remaining graph is connected. Our answer would then be dp[n - 1][j] for all j. This DP definition is incomplete, but in a contest, you're most likely to come up with this definition in the first try.
So, what's the flaw with this DP definition? It only captures states which are directly useful. Since j_1 + j_2 could've become equal to k, in this case, we could have 2 disconnected graphs which would've combined to created a connected one.
Now we know that we are missing indirectly useful states in our DP table, but we are not sure which ones exactly. Whenever you face this Dilemma, just start the algorithm from the 0^{th} element, and you'll quickly realize what you're missing.
Notice that each block can contain at most 3 edges. Label them as top, bot and mid edges.
In subset sum DP, the elements are processed in an online fashion. Meaning, we first compute our answer assuming that we only have the prefix [0, ... i] and we investigate the transitions when we introduce the i^{th} element. We then make one of 2 choices for the i^{th} element: Take or Leave. So, let's start with the first block. It only has a mid edge. We can either take it or leave it, which leaves us with 2 possibilities. Notice that our current DP does not handle the leave case, because it makes the graph disconnected. But we can see that it's a valid choice since the adjacent block can make it connected. This is our first hint on the new state that we need to introduce.
Now, consider the second block, it has 3 edges, top, bot and mid. We can take or leave each edge independently, so there are 8 possibilities. Let us list down all 2*8 possibilities for both blocks combined. (The first column of result assumes that we kept the mid edge of the 0^{th} block and the second column assumes that we ignored it).
Can you spot the directly useful, indirectly useful and hopeless states from this graph? All states with one connected component are directly useful, and all the states where at least one connected component is isolated from the the incoming block is hopeless. Since that incoming block can only interact with the terminal x and x*, we can conclude that any element which is a part of a connected component not containing x or x* is hopeless, because no matter what you do later, you cannot make the entire graph connected. Hence, for a state to be not hopeless, it should have no connected component not containing x or x*.
However, the editorial ignores all the hopeless states, which makes you wonder how did they suddenly guess that there can only be 2 states. But let's not do that, let's define 3 states, connected, two_connected, and hopeless, where two_connected represents an indirectly useful state where there are at most 2 connected components containing the terminal vertices. Although we keep saying 2-connected, we actually mean, the graph should have 2 connected components and with at least one of the terminal blocks. With these hints, we are now ready to define the actual DP definition:
Define dp[i][j][state] to be the number of ways to delete exactly j vertices from blocks [0, ... i] such that the resulting graph is in the given state (connected, two_connected, hopeless).
To perform the transitions, like subset-sum DP, we make 8 choices on the last block and take contribution from the previous states accordingly.
A hopeless state can only lead to a hopeless state.
If the last state was connected, and we drop the terminal top and bot edges, it'd become hopeless. If we take at least 2 terminal edges out of top, bot and mid, the graph would remain connected, else it becomes 2 connected.
If the last state was two-connected, we are not allowed to drop the terminal top and bot edges. If we do, it leads to a hopeless state. Depending on whether we keep the terminal mid edge, it'll either lead us to connected or two_connected graph.
Since we eventually won't use hopeless states, it does not matter whether we fill the correct values in it. And that's what the editorial does, ignore it altogether, but in my implementation, I do include some parts of it for clarity.