第 3 题 Papričice (papriice)

时间限制 1.0 s · 空间限制 256 MB · 20 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 papriice.in，输出文件 papriice.out。

题目描述

给定一个 $n$ 个点的树，这 $n$ 个点编号为 1 到 $n$。

现在要选择断掉两条边，会形成三个连通块，假设这三个连通块内的点数分别为 $a, b, c$，那么您要做的就是最小化 $\max a, b, c - \min a, b, c$ 的大小，求这个最小值。

输入格式

第一行一个整数 $n$ 代表树的点数。

接下来 $n - 1$ 行每行两个整数 $x, y$ 代表树的一条边。

输出格式

一行一个整数代表答案。

样例

样例 1

输入：

4
1 2
2 3
3 4

输出：

1

样例 2

输入：

6
1 2
1 3
3 4
3 5
5 6

输出：

0

样例 3

输入：

9
1 3
2 3
3 4
3 5
5 6
5 7
7 8
7 9

输出：

2

提示

样例 1 解释

能构造的最优解三个连通块的点数都为 $1, 1, 2$，所以输出 $2 - 1 = 1$。

样例 2 解释

断掉点 1 到点 3 的边，点 3 到点 5 的边，形成的三个连通块点数相同。

样例 3 解释

如下图所示：

数据规模与约定

本题采用捆绑测试。

• 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$。

对于 100% 的数据，$1 \le x, y \le n$。

本题满分 110 分。

说明

](https://hsin.hr/coci/archive/2020_2021/contest1_tasks.pdf)。