P7165 [COCI 2020/2021 #1] Papričice

Given a tree with $n$ nodes, the nodes are numbered from $1$ to $n$. Now you need to cut (remove) two edges. This will split the tree into three connected components. Suppose the numbers of nodes in these three components are $a, b, c$. Your task is to minimize $\max\{a,b,c\}-\min\{a,b,c\}$, and output this minimum value.

The first line contains an integer $n$, the number of nodes in the tree. The next $n-1$ lines each contain two integers $x, y$, representing an edge of the tree.

Output one integer in a single line, representing the answer.

#### Sample 1 Explanation An optimal solution can make the sizes of the three connected components $1,1,2$, so the output is $2-1=1$. #### Sample 2 Explanation Cut the edge between node $1$ and node $3$, and the edge between node $3$ and node $5$. The three resulting connected components have the same number of nodes. #### Sample 3 Explanation As shown in the figure below:  #### Constraints **This problem uses bundled testdata.** - Subtask 1 (15 pts): $3 \le n \le 200$. - Subtask 2 (35 pts): $3 \le n \le 2000$. - Subtask 3 (60 pts): $3 \le n \le 2 \times 10^5$. For $100\%$ of the testdata, $1 \le x,y \le n$. **The full score for this problem is $110$ points.** #### Notes Translated from [Croatian Open Competition in Informatics 2020 ~ 2021 Round 1 D Papričice ](https://hsin.hr/coci/contest1_tasks.pdf)。 Translated by ChatGPT 5