题目描述

给定一颗 $n$ 个节点的有根树，规定节点 $1$ 为该树的根。

定义 $l=(c_1,c_2,\cdots,c_m)$ 是树上的一条合法路径，当且仅当其满足：

1. 对于 $\forall 1\le i\lt m$，树上存在一条边 $(c_i,c_{i+1})$；
2. $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)}$：无特殊限制。