codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.