ECOO '19 R3 P4 - Network - Olympiads Online Judge

ECOO '19 R3 P4 - Network

View as PDF

Submit solution

All submissions

Best submissions

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$ $N$ machines in total.
One of the machines is denoted as the "master" and is responsible for broadcasting new data.
There are $N-1$ $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$ $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$ $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$ $N$ , $R$ $R$ $(1 \le N, R \le 100\,000)$ $(1 \leq N, R \leq 100 000)$ , the number of machines and the maximum distance that each machine can be from a master machine. Machines are numbered from $1$ $1$ to $N$ $N$ . The next $N-1$ $N - 1$ lines each contain two distinct integers $A_i$ $A_{i}$ , $B_i$ $B_{i}$ $(1 \le A_i, B_i \le N)$ $(1 \leq A_{i}, B_{i} \leq N)$ stating that there is a one-directional wire from $A_i$ $A_{i}$ to $B_i$ $B_{i}$ .

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

Output Specification

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

Sample Input (Two Datasets Shown)

Copy

Sample Output

Copy

1
2

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

Comments

11

charliezhao06 commented on March 8, 2020, 8:27 p.m. ← edit 4 →

Hello stranger

2

pblpbl commented on March 8, 2020, 9:39 p.m.

Hi (not so obscure now, hopefully)