Torrent
레이팅 미적용의견: 0
Mirko works at a data centre and today’s task is to copy a file sized 1 GiB to \(n\) computers. The computers
are denoted with integers from 1 to \(n\) and are connected so that they form a \(so-ca\)lled tree. More precisely,
\(n - 1\) pairs of computers are directly connected via network cable in a way that there is a unique path
between each pair of computers.
1
2
5
3
4
6
1
2
5
3
4
6
1
2
5
3
4
6
Figure 4: In the first sample test, it takes two minutes for the file to be copied to all computers.
Initially, Mirko manually placed the file on two different computers – computer \(a\) and computer \(b\) and is
now writing commands that will copy the file to all other computers. The file can be copied from computer
\(x\) to computer \(y\) only if the two computers are directly connected, and the copying process takes exactly
one minute. At any moment, each individual computer can take part in at most one copying process, but
it is allowed to have the file being copied between arbitrarily many different pairs of computers at the
same time. Therefore, when the copying process ends from computer \(x\) to computer \(y\), it is possible in the
next minute to copy the file from computer \(x\) to computer \(w\) and from computer \(y\) to computer \(z\).
Determine the minimal amount of time it takes for the file to be copied to all computers.
Subtask
Score
Limitations
1
31
\(2 \le n \le 1\,000\)
2
69
\(1\,000 \le n \le 300\,000\)
7 od 8
The first line of input contains the integer \(n\) and two different integers \(a\) and \(b\) (\(1 \le a\), \(b \le n\)) – the number
of computers and the labels of the computers already containing the file. Each of the following \(n - 1\) lines
contains two different integers \(x\) and \(y\) (\(1 \le x\), \(y \le n\)) – the labels of the computers directly connected via
network cable. The computer network forms a tree, as described in the task.
Input
You must output the required minimal amount of time in minutes.
Scoring
Subtask
Score
Limitations
1
31
\(2 \le n \le 1\,000\)
2
69
\(1\,000 \le n \le 300\,000\)
7 od 8
6 2 1
1 2
2 3
2 4
1 5
5 6
2
10 1 2
1 2
2 5
1 3
1 4
4 6
6 7
3 8
3 9
3 10
4
17 1 2
1 3
1 4
4 6
6 7
3 8
3 9
3 10
1 13
13 5
13 11
13 12
13 14
14 15
15 16
15 17
14 2
5
평가 및 의견
Torrent
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Torrent