题目描述
给定一颗 $n$ 个节点的有根树，规定节点 $1$ 为该树的根。
定义 $l=(c_1,c_2,\cdots,c_m)$ 是树上的一条合法路径，当且仅当其满足：
- 对于 $\forall 1\le i\lt m$，树上存在一条边 $(c_i,c_{i+1})$；
- $c_1=1$。
记该路径的权值 $v_l$ 为其总长度 $m-1$。
构造一个路径集 $S=\left\{l_1,\cdots,l_k\right\}$，使得对于树上任意点 $1\le x\le n$，至少存在一个 $l_j\in S$ 满足 $x$ 存在于其路径上。记此路径集的权值 $V_S$ 为其包含的所有路径的权值之和，即 $V_S=v_{l_1}+\cdots+v_{l_k}$。
最小化 $V_S$，并输出这个值。
输入格式
第一行一个整数 $n$。
后面 $n-1$ 行，每行两个数 $x,y$，表示一条树上的边 $(x,y)$。
输出格式
一行共一个整数，表示满足要求的最小的 $V_S$。
样例输入 #1
6
1 2
2 3
1 4
2 5
5 6样例输出 #1
6样例解释 #1
该树可以构造出满足要求的路径集 $S=\left\{(1,4),(1,2,3,2,5,6)\right\}$，其权值为 $6$。
值得注意的是，另一个满足要求的路径集 $S_2=\left\{(1,4),(1,2,3),(1,2,5,6)\right\}$ 权值亦为 $6$。
容易证明不存在一个合题路径集使得其权值小于 $6$。
样例输入 #2
5
1 2
2 3
3 4
4 5样例输出 #2
4数据规模与约定
注意，按照题目的定义，路径经过的点是可重的。
本题目采用 $\text{subtask}$ 测试。
对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le x,y\le n$。
具体数据范围如下：
$\text{subtask 1(10pts)}$：$1\le n\le 5$；
$\text{subtask 2(20pts)}$：$1\le n\le 100$；
$\text{subtask 3(20pts)}$：$1\le n\le 1000$；
$\text{subtask 4(20pts)}$：$1\le n\le 10^5$；
$\text{subtask 5(30pts)}$：无特殊限制。
