2167F.md (2892B)
1 Source: https://codeforces.com/problemset/problem/2167/F 2 3 F. Tree, TREE!!! 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Roots change, but the tree stands strong — so should your logic. 22 23 Behruzbek received a tree$^{\text{∗}}$ with $n$ nodes. For a chosen root$^{\text{†}}$ $r$, Behruzbek wants to find cuteness of the tree. 24 25 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. 26 27 After discovering the cuteness of trees, Behruzbek became interested in finding the kawaiiness of the tree! Kawaiiness is defined as: 28 29 $$ \sum_{r = 1}^{n} |S_r| = |S_1| + |S_2| + \dots + |S_n| $$ 30 31 Unfortunately, Behruzbek is feeling sleepy now. Please help Behruzbek by finding the kawaiiness of the tree! 32 33 $^{\text{∗}}$A tree is a connected graph without cycles. 34 35 $^{\text{†}}$A rooted tree is a tree where one vertex is special and called the root. 36 37 Input 38 39 The first line contains the number of test cases $t$ ($1 \leq t \leq 10^{4}$). 40 41 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. 42 43 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. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^{5}$. 46 47 Output 48 49 For each test case, output one integer — the value of $\sum\limits_{r=1}^n |S_r|$. 50 51 Example 52 53 Input 54 55 ``` 56 4 57 58 2 2 59 60 1 2 61 62 5 3 63 64 1 2 65 66 1 3 67 68 1 4 69 70 1 5 71 72 6 3 73 74 1 2 75 76 1 3 77 78 2 4 79 80 2 5 81 82 3 6 83 84 10 5 85 86 5 6 87 88 4 9 89 90 3 9 91 92 2 6 93 94 2 8 95 96 8 9 97 98 6 10 99 100 1 6 101 102 4 7 103 ``` 104 105 Output 106 107 ``` 108 2 109 110 9 111 112 17 113 114 35 115 ``` 116 117 Note 118 119 Let $f(i) = |S_i|$ 120 121 For the third example: 122 123 * 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$. 124 * 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$. 125 * Root is $3$, $f(3) = 3$. For example, node $3$ can be obtained by choosing: $LCA(2, 4, 6) = 3$. 126 * Root is $4$, $f(4) = 3$. For example, node $2$ can be obtained by choosing: $LCA(1, 3, 5) = 2$. 127 * Root is $5$, $f(5) = 3$. For example, node $2$ can be obtained by choosing: $LCA(3, 4, 6) = 2$. 128 * Root is $6$, $f(6) = 4$. For example, node $3$ can be obtained by choosing: $LCA(3, 4, 5) = 2$. 129 130 Overall, $2 + 2 + 3 + 3 + 3 + 4 = 17$.