레이팅 미적용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.
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