#2027. 剪辣椒

内存限制
512 MiB
时间限制
2000 ms
文件输入输出
chilli.in ≫ chilli.out
题目类型
传统
评测方式
文本比较
上传者 admin

显示标签

题目描述

给定一棵树,删掉其中的两条边,使得三个部分的点数的极差最小,求极差的最小值。

输入格式 chilli.in

第一行一个整数 ,表示树的大小,结点从 进行编号。

下面 行每一行包含两个整数 ,表示结点 和结点 之间有一条边相连。

输出格式 chilli.out

输出最小极差。

样例

输入 #1

4
1 2
2 3
3 4

输出 #1

1

输入 #2

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

输出 #2

2

数据范围与提示

子任务 限制 分值
1 15
2 35
3 50