Papricice
레이팅 미적용의견: 0
Afrika paprika! – S.V.
After a tiring morning in the garden, Mr. Malnar decided to reward himself with dried hot peppers he
grew himself.
He has \(n\) peppers, connected with \(n - 1\) pieces of string, so that every two peppers are connected by some
series of strings. Formally, they form a tree.
Mr. Malnar will partake in three lunches today. For that purpose, he will cut two strings to get three
smaller components, one for each lunch.
1
2
3
4
5
6
7
8
9
The tree from the third example along with the optimal cuts.
It’s bad to make any lunch too spicy, so he will choose the cuts in a way that minimises the difference
between the size of the largest and the smallest component. You need to determine the sought
minimum difference.
Subtask 1 (15 points): \(3 \le n \le 200\)
Subtask 2 (35 points): \(3 \le n \le 2000\)
Subtask 3 (60 points): \(3 \le n \le 200\,000\)
The first line contains an integer \(n\), the number of peppers. The peppers are labeled by integers from 1 to
\(n\).
Each of the following \(n - 1\) lines contains two integers \(x\) and \(y\) (\(1 \le x\), \(y \le n\)) – labels of peppers that are
directly connected by a piece of string.
Print the minimum possible difference of component sizes.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(3 \le n \le 200\) |
2 | 35점 | \(3 \le n \le 2000\) |
3 | 60점 | \(3 \le n \le 200\,000\) |
4
1 2
2 3
3 4
1
6
1 2
1 3
3 4
3 5
5 6
0
9
1 3
2 3
3 4
3 5
5 6
5 7
7 8
7 9
2
평가 및 의견
Papricice
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Papricice