7476. [GESP202609 六级] 分树规划
时间限制：1000 MS 内存限制：256 MB
题目描述
#### 题目描述 老师有一棵有 $n$ 个结点的树，结点依次以 $1,2,\ldots,n$ 编号。 老师想将这棵树作为奖品分给两位同学。具体而言，老师会选择一条边并从树上删去它，从而将这棵树分为两个连通块。两位同学分别可以得到其中一个连通块。 如果有同学拿到的连通块结点数明显小于另一位同学，那么这位同学会不太高兴。为了避免这种情况出现，老师想知道两个连通块结点数之差的绝对值最小是多少。 #### 输入格式 第一行，一个正整数 $n$，表示结点数量。 接下来 $n-1$ 行，每行两个正整数 $u_i,v_i$，表示一条连接结点 $u_i$ 和结点 $v_i$ 的边。 #### 输出格式 输出一行，一个整数，表示答案。 #### 输入输出样例 #1 ##### 输入 #1 ``` 4 1 2 2 3 3 4 ``` ##### 输出 #1 ``` 0 ``` #### 输入输出样例 #2 ##### 输入 #2 ``` 6 1 2 1 3 1 4 1 5 5 6 ``` ##### 输出 #2 ``` 2 ``` #### 说明/提示 对于 $40\%$ 的测试点，保证 $2\le n\le 500$。 对于所有测试点，保证 $2\le n\le 2\times 10^4$。