Think about BFS order.

Try some DP.

As in the hint, consider the "layers" formed by processing the nodes in the graph in BFS order from ~1~. For this subtask, let's try all possible layers. Given a bitmask, we can make a mapping to layers by considering the ~1~s as "separators". There are ~2^{N-2}~ possible arrangements, corresponding to ways to choose some of the positions ~2, 3, \dots, N~ to increase the distance by ~1~, where position ~2~ must be chosen (so that position ~1~, the source, is the only node with a distance of ~0~), and we can brute force all of them.

We can add up the distances from choosing a node as node ~N~ and rearranging the rest of the nodes with some combinatorics, so it suffices to count the number of possible graphs if the nodes in these layers are fixed. Note that we only need all edges to be either within the same layer or cross between two adjacent layers, and each node much have at least one edge to its previous layer.

We can use dynamic programming, with a state similar to (number of nodes processed so far, number of edges used so far), where the transitions consider all possibilities for the number of edges the current node uses (using some more combinatorics to count the number of ways to arrange them).

Time Complexity: ~\mathcal O(N^2 \cdot R \cdot 2^N)~, or with slower polynomial factors.

For this subtask, let's do some different DP. Use a state of (number of nodes processed so far, number of edges used so far, number of nodes in the last layer). We must also be careful about where ~N~ is, so let's store three numbers per state. One, the number of paths. Two, the sum of the path lengths. Three, assuming node ~N~ has been placed, the sum of path lengths. We need not store the number of paths if ~N~ has been placed, since the only reason we store the number of paths in the first place is so that we can maintain the sum of lengths.

When transitioning, consider all possible next layer sizes, and new edges. We then need to calculate the number of ways to 1) connect all new nodes to the previous layer and 2) add the remaining edges, possibly with some between edges in this layer.

To do this efficiently, we can precompute using some DP. For the DP, the state is (previous layer nodes, new layer nodes, edges available). We transition by either creating a new layer, or building on the current layer. Full details are left as an exercise.

Time Complexity: ~\mathcal O(N^3R^2)~, or possibly ~\mathcal O(N^3R^3)~.

What if you used a generating function, or polynomial?

Note that the number of edges is actually irrelevant to our state, that is, although we must store it, it does not factor into our transitions at all.

We can change our state to (total nodes, nodes in last layer), and store a polynomial (some may know it as a generating function). Why would we do this?

Imagine adding nodes to our layer one at a time. Let ~c~ be the current size of the layer and ~p~ be the size of the previous layer. Then our polynomial is multiplied by:

$$\displaystyle ((x + 1)^p - 1)(x + 1)^c$$

We need to connect at least one previous layer node to the new node, and we can have up to ~p~, so we have ~(x + 1)^p - 1~. We can optionally have up to ~c~ between-layer edges, so we have ~(x + 1)^c~.

Using this generating function, we can speed up our transitions drastically.

Time Complexity: ~\mathcal O(N^4R)~

We have polynomials in base ~x~. Might another base be better?

We should use a base of ~x + 1~ instead of ~x~ for our polynomial. This way instead of an ~\mathcal O(NR)~ multiplication at each step, we get ~\mathcal O(N^2)~.

Specifically, our polynomial before was a vector of coefficients like:

$$\displaystyle \sum_{i = 0} a_ix^i$$

Let's make it:

$$\displaystyle \sum_{i = 0} a_i(x + 1)^i$$

Notably, we must keep all terms of the polynomial, unlike the last subtask, since higher terms are not irrelevant anymore.

We can expand the polynomial at the end to get our final answer.

Time Complexity: ~\mathcal O(N^5)~