CF2167F Tree, TREE!!!

Roots change, but the tree stands strong — so should your logic. Behruzbek received a tree $ ^{\text{∗}} $ with $ n $ nodes. For a chosen root $ ^{\text{†}} $ $ r $ , Behruzbek wants to find cuteness of the tree. Consider every set of $ k $ distinct nodes of the tree. For each such set, compute its lowest common ancestor ([LCA](https://en.wikipedia.org/wiki/Lowest_common_ancestor)) in the tree when it is rooted at $ r $ . Let $ S_r $ be the set of all distinct nodes obtained this way; then cuteness of the tree is $ |S_r| $ , where $ |S| $ means the number of distinct elements. After discovering the cuteness of trees, Behruzbek became interested in finding the kawaiiness of the tree! Kawaiiness is defined as: $$$ \sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \dots + |S_n| $$$ Unfortunately, Behruzbek is feeling sleepy now. Please help Behruzbek by finding the kawaiiness of the tree! $ ^{\text{∗}} $ A tree is a connected graph without cycles. $ ^{\text{†}} $ A rooted tree is a tree where one vertex is special and called the root.

The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10^{4} $ ). The first line of each test case contains two integers $ n $ and $ k $ ( $ 2 \leq k \leq n \leq 2\cdot 10^{5} $ ) — the number of vertices in the tree and the number of distinct integers to be chosen. The following $ n-1 $ lines of each test case describe the tree. Each of the lines contains two integers $ u $ and $ v $ ( $ 1 \leq u,v \leq n $ , $ u \ne v $ ) that indicate an edge between vertex $ u $ and $ v $ . It is guaranteed that these edges form a tree. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^{5} $ .

For each test case, output one integer — the value of $ \sum\limits_{r=1}^n |S_r| $ .

Let $ f(i) = |S_i| $ For the third example: - Root is $ 1 $ , only $ 1 $ and $ 2 $ nodes can be obtained. For example, we can choose: $ LCA(4, 5, 6) = 1 $ and $ LCA(2, 4, 5) = 2 $ . As a result, $ f(1) = 2 $ . - Root is $ 2 $ , only $ 1 $ and $ 2 $ nodes can be obtained. For example, we can choose: $ LCA(1, 3, 6) = 1 $ and $ LCA(1, 4, 5) = 2 $ . As a result, $ f(2) = 2 $ . - Root is $ 3 $ , $ f(3) = 3 $ . For example, node $ 3 $ can be obtained by choosing: $ LCA(2, 4, 6) = 3 $ . - Root is $ 4 $ , $ f(4) = 3 $ . For example, node $ 2 $ can be obtained by choosing: $ LCA(1, 3, 5) = 2 $ . - Root is $ 5 $ , $ f(5) = 3 $ . For example, node $ 2 $ can be obtained by choosing: $ LCA(3, 4, 6) = 2 $ . - Root is $ 6 $ , $ f(6) = 4 $ . For example, node $ 3 $ can be obtained by choosing: $ LCA(3, 4, 5) = 2 $ . Overall, $ 2 + 2 + 3 + 3 + 3 + 4 = 17 $ .