分树规划
EXY-PG-0244
题目描述
老师有一棵有 $n$ 个结点的树，结点依次以 $1,2,…,n$ 编号。
老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。
如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。
输入格式
第一行，一个正整数 $n$，表示结点数量。
接下来 $n−1$ 行，每行两个正整数 $u_{i},v_{i}$，表示一条连接结点 $u_{i}$ 和结点 $v_{i}$ 的边。
输出格式
输出一行，一个整数，表示答案。
样例说明
样例 1
输入：
4
1 2
2 3
3 4
输出：
0样例 2
输入：
6
1 2
1 3
1 4
1 5
5 6
输出：
2数据范围
对于 40% 的测试点，保证 $2≤n≤500$。
对于所有测试点，保证 $2≤n≤2×10^{4}$。