ECOO '19 R3 P4 - Network

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 13.0s
Memory limit: 512M

Problem type

Naomi works in a data center and has designed a new computer broadcast network which has the following structure:

  • There are N machines in total.
  • One of the machines is denoted as the "master" and is responsible for broadcasting new data.
  • There are N-1 one-directional wires between machines in the network arranged in a way such that the master machine can contact all the other machines.

Such a network would require minimal infrastructure and allow the master machine to broadcast information while being insulated from the other machines.

Unfortunately, the interns tasked with implementing the network made two mistakes. First, they mixed up the directions of some of the one-directional wires. Second, they used a low-quality wire with high signal loss, which means that a given machine can only communicate with machines at most R connections away.

Nevertheless, Naomi remained optimistic: if she assigns multiple machines to the master role in such a way that each machine is at most R connections away from a master machine, then the network can still function. As Naomi's star intern, can you help her figure out the minimum number of master machines that are required?

Input Specification

The input will contain 10 datasets. Each dataset begins with two integers N, R (1 \le N, R \le 100\,000), the number of machines and the maximum distance that each machine can be from a master machine. Machines are numbered from 1 to N. The next N-1 lines each contain two distinct integers A_i, B_i (1 \le A_i, B_i \le N) stating that there is a one-directional wire from A_i to B_i.

For the first 3 cases, N \le 20.
For the first 6 cases, N \le 100.

Output Specification

For each dataset, output the minimum number of master machines required to make the network operational.

Sample Input (Two Datasets Shown)

2 1
1 2
4 2
1 3
2 3
3 4

Sample Output

1
2

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments


  • 0
    ChrisLi  commented on July 3, 2020, 3:28 a.m.

    This question should worth 20 marks.


  • 10
    charliezhao06  commented on March 8, 2020, 4:27 p.m. edit 3

    Meme

    Hello stranger


    • 1
      pblpbl  commented on March 8, 2020, 5:39 p.m.

      Hi (not so obscure now, hopefully)