J9 实践-5 牛妹的最小树

题目描述

牛妹有一张连通图，由 $n$ 个点和 $n-1$ 条边构成，也就是说这是一棵树，牛妹可以任意选择一个点为根，根的深度$dep_{root}$为0，对于任意一个非根的点，我们将他到根节点路径上的第一个点称作他的父节点，例如 $1$ 为根，$1-4$ 的路径为 $1-3-5-4$ 时，$4$ 的父节点是$5$，并且满足对任意非根节点，$dep_i=dep_{fa_i}+1$，整棵树的价值 $W=\sum\limits_{i=1}^n dep_i$，即所有点的深度和。

牛妹希望这棵树的 $W$ 最小，请你告诉她，选择哪个点可以使 $W$ 最小。

输入格式

第一行，一个数，$n$； 接下来 $n-1$ 行，每行两个数 $x,y$，代表 $x-y$ 是树上的一条边。

输出格式

一行，一个数，最小的 $W$。

样例输入

4
1 2
1 3
1 4

样例输出

3

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le N \le 10^6$。