Equidistant Vertices
Contest: Codeforces Round 734 (Div. 3)
Difficulty rating: 2200
Tags: brute force, combinatorics, dfs and similar, dp, trees

A tree is an undirected connected graph without cycles.

You are given a tree of $$$n$$$ vertices. Find the number of ways to choose exactly $$$k$$$ vertices in this tree (i. e. a $$$k$$$-element subset of vertices) so that all pairwise distances between the selected vertices are equal (in other words, there exists an integer $$$c$$$ such that for all $$$u, v$$$ ($$$u \ne v$$$, $$$u, v$$$ are in selected vertices) $$$d_{u,v}=c$$$, where $$$d_{u,v}$$$ is the distance from $$$u$$$ to $$$v$$$).

Since the answer may be very large, you need to output it modulo $$$10^9 + 7$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case is preceded by an empty line.

Each test case consists of several lines. The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le k \le n \le 100$$$) — the number of vertices in the tree and the number of vertices to be selected, respectively. Then $$$n - 1$$$ lines follow, each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.

Output format:
For each test case output in a separate line a single integer — the number of ways to select exactly $$$k$$$ vertices so that for all pairs of selected vertices the distances between the vertices in the pairs are equal, modulo $$$10^9 + 7$$$ (in other words, print the remainder when divided by $$$1000000007$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3

4 2
1 2
2 3
2 4

3 3
1 2
2 3

5 3
1 2
2 3
2 4
4 5

Example output:
6
0
1

Editorial:
If $$$k = 2$$$, any set of two vertices may be taken so the answer is $$$\frac{n(n - 1)}{2}$$$ modulo $$$10^9 + 7$$$.
Suppose $$$k \ge 3$$$. Consider three vertices $$$A$$$, $$$B$$$, $$$C$$$ such that $$$d_{A, B} = d_{A,C} = d_{B,C}$$$. If this equality is true, there's a vertex $$$Q$$$ that belongs to all three paths, otherwise, either one of the vertices belongs to the path between two others or there is more than one simple path (i. e. path having distinct edges) between any of the vertices so the graph isn't a tree. Hence, the following equalities are true:
$$$$$$d_{A,B} = d_{A,Q} + d_{B,Q},$$$$$$ $$$$$$d_{A,C} = d_{A,Q} + d_{C,Q},$$$$$$ $$$$$$d_{B,C} = d_{B,Q} + d_{C,Q}.$$$$$$
Then
$$$$$$d_{A,Q} + d_{B,Q} = d_{A,Q} + d_{C,Q},$$$$$$ $$$$$$d_{A,Q} + d_{B,Q} = d_{B,Q} + d_{C,Q},$$$$$$ $$$$$$d_{A,Q} + d_{C,Q} = d_{B,Q} + d_{C,Q},$$$$$$
hence, $$$d_{A,Q} = d_{B,Q} = d_{C,Q}$$$.
Suppose $$$k > 3$$$. Let's select vertices $$$A$$$, $$$B$$$, $$$C$$$, $$$D$$$ that is a correct desired set of four vertices, for the triple of paths $$$AB$$$, $$$AC$$$, $$$BC$$$ let's select a common vertex $$$Q$$$ and for the triple $$$BC$$$, $$$CD$$$, $$$BD$$$ — $$$Q'$$$. Because
$$$$$$d_{B,Q} = d_{C,Q},$$$$$$ $$$$$$d_{B,Q'} = d_{C,Q'}$$$$$$
$$$Q$$$ is the same vertex as $$$Q'$$$. The same procedure we can do for all other pairs of triples of vertices. The situation will not be another if we add a new vertex in the set if the set will still meet the problem's conditions. So if $$$k \ge 3$$$, a vertex $$$Q$$$ exists such that all vertices of the set are equidistant from it.
Note that for each set only one such $$$Q$$$ exists. Let's iterate over all vertices taking them as $$$Q$$$ and "hang" the tree by $$$Q$$$. The set of $$$k$$$ vertices equidistant from $$$Q$$$ meets the problem's condition if and only if the vertices of the set are placed in different subtrees of vertices adjacent to $$$Q$$$ (in other words, the paths from them to $$$Q$$$ must intersect only in $$$Q$$$).
Let's calculate the number of desired sets for a given $$$Q$$$ and a layer of equidistant vertices. Let $$$L_Q$$$ be the number of vertices adjacent to $$$Q$$$ (and it's the number of subtrees, too). Let's create an array $$$cnt$$$ ($$$1$$$-indexed) of size $$$L_Q$$$ so that the $$$i$$$-th element will contain the number of the vertices of the layer in the $$$i$$$-th subtree. For the layer of vertices adjacent to $$$Q$$$, this array will be filled with $$$1$$$. For the other layers, we can update the array as follows: let's mark $$$Q$$$ and vertices adjacent to $$$Q$$$ as used, then for every vertex of the current layer let's decrease $$$cnt[i]$$$ by $$$1$$$ if $$$i$$$ is the index of the subtree of the vertex, then let's increase $$$cnt[i]$$$ by the number of the vertices adjacent to the current one but not used. Then let's mark the vertices as used. After the iteration, the array $$$cnt$$$ will correspond to the new layer.
Using the array, let's calculate the number of the desired sets of $$$k$$$ vertices using the concept of dynamic programming. Let's create an array $$$dp$$$ ($$$0$$$-indexed) of size $$$(L_Q + 1) \times (k + 1)$$$. $$$dp[i][j]$$$ will contain a number of found sets of $$$j$$$ vertices if only $$$i$$$ subtrees have been considered. Let's fill the array with $$$0$$$ except $$$dp[0][0] = 1$$$. Let's start a $$$for$$$-loop with parameter $$$i$$$ from $$$0$$$ to $$$L_Q - 1$$$ and the internal one with parameter $$$j$$$ from $$$0$$$ to $$$k$$$. In every step, we can either take a vertex from $$$(i + 1)$$$-th subtree or take nothing.
If we take a vertex from the subtree (it's possible only if $$$j < k$$$), then we have $$$cnt[i + 1] \cdot dp[i][j]$$$ ways to select $$$j + 1$$$ vertices considering $$$i + 1$$$ subtrees so that the last vertex belongs to the $$$(i + 1)$$$-th subtree. This value we must add to $$$dp[i + 1][j + 1]$$$ that must contain all ways to select $$$j + 1$$$ vertices from $$$i + 1$$$ subtrees.
If we ignore the subtree, the number of ways to select $$$j$$$ vertices from $$$i + 1$$$ subtrees ignoring the $$$(i + 1)$$$-th subtree is $$$dp[i][j]$$$. It must be added to the number of ways to select $$$j$$$ vertices from $$$i + 1$$$ subtrees — $$$dp[i + 1][j]$$$.
The answer for the current $$$Q$$$ and the current layer of equidistant vertices is $$$dp[L_Q][k]$$$. The answer for the whole tree is the sum of the answers for all $$$Q$$$ and for all layers of equidistant vertices. Remember that all arithmetical operations must be done modulo $$$10^9 + 7$$$.
The number of possible central vertices is $$$n$$$. For every central vertex and every layer we perform two actions: recalculate the array $$$cnt$$$ and calculate the number of the corresponding sets using the concept of dynamic programming. The recalculation of $$$cnt$$$ works in $$$O(L_Qk)$$$, it's just BFS starting from $$$Q$$$ so for every central vertex it works in O(n). The dynamic programming for the current $$$Q$$$ and the current layer works in $$$O(L_Qk)$$$, for the current $$$Q$$$ and all layers — in $$$O(nL_Qk)$$$. The summary time corresponding to the current $$$Q$$$ is $$$O(nL_Qk)$$$.
The total algorithm work time is $$$\sum\limits_{Q = 1}^{n} O(nL_QK) = O(nk\sum\limits_{Q = 1}^{n} L_Q)$$$. The sum of all $$$L_Q$$$ is a total number of the adjacent vertices to all vertices, it's just a double number of edges — $$$2(n - 1)$$$. So the total work time is $$$O(n^2k)$$$.