F. Tree, TREE!!!time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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) 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. InputThe 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}$$$.OutputFor each test case, output one integer — the value of $$$\sum\limits_{r=1}^n |S_r|$$$.ExampleInput42 21 25 31 21 31 41 56 31 21 32 42 53 610 55 64 93 92 62 88 96 101 64 7Output291735NoteLet $$$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$$$.