codeforces-scrape

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

1689C.md (2378B)


      1 Source: https://codeforces.com/problemset/problem/1689/C
      2 
      3 C. Infected Tree
      4 
      5 time limit per test
      6 
      7 3 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 Byteland is a beautiful land known because of its beautiful trees.
     22 
     23 Misha has found a binary tree with $n$ vertices, numbered from $1$ to $n$. A binary tree is an acyclic connected bidirectional graph containing $n$ vertices and $n - 1$ edges. Each vertex has a degree at most $3$, whereas the root is the vertex with the number $1$ and it has a degree at most $2$.
     24 
     25 Unfortunately, the root got infected.
     26 
     27 The following process happens $n$ times:
     28 
     29 * Misha either chooses a non-infected (and not deleted) vertex and deletes it with all edges which have an end in this vertex or just does nothing.
     30 * Then, the infection spreads to each vertex that is connected by an edge to an already infected vertex (all already infected vertices remain infected).
     31 
     32 As Misha does not have much time to think, please tell him what is the maximum number of vertices he can save from the infection (note that deleted vertices are not counted as saved).
     33 
     34 Input
     35 
     36 There are several test cases in the input data. The first line contains a single integer $t$ ($1\leq t\leq 5000$) — the number of test cases. This is followed by the test cases description.
     37 
     38 The first line of each test case contains one integer $n$ ($2\leq n\leq 3\cdot 10^5$) — the number of vertices of the tree.
     39 
     40 The $i$-th of the following $n-1$ lines in the test case contains two positive integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$), meaning that there exists an edge between them in the graph.
     41 
     42 It is guaranteed that the graph is a binary tree rooted at $1$. It is also guaranteed that the sum of $n$ over all test cases won't exceed $3\cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, output the maximum number of vertices Misha can save.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 2
     56 
     57 1 2
     58 
     59 4
     60 
     61 1 2
     62 
     63 2 3
     64 
     65 2 4
     66 
     67 7
     68 
     69 1 2
     70 
     71 1 5
     72 
     73 2 3
     74 
     75 2 4
     76 
     77 5 6
     78 
     79 5 7
     80 
     81 15
     82 
     83 1 2
     84 
     85 2 3
     86 
     87 3 4
     88 
     89 4 5
     90 
     91 4 6
     92 
     93 3 7
     94 
     95 2 8
     96 
     97 1 9
     98 
     99 9 10
    100 
    101 9 11
    102 
    103 10 12
    104 
    105 10 13
    106 
    107 11 14
    108 
    109 11 15
    110 ```
    111 
    112 Output
    113 
    114 ```
    115 0
    116 2
    117 2
    118 10
    119 ```
    120 
    121 Note
    122 
    123 In the first test case, the only possible action is to delete vertex $2$, after which we save $0$ vertices in total.
    124 
    125 In the second test case, if we delete vertex $2$, we can save vertices $3$ and $4$.
    126 
    127  ![](https://espresso.codeforces.com/8fac67159a6807af6626efa4ed0a466df8c67825.png)