题目内容

在一片山区中，设有 $n$ 个通信基站，它们通过光纤连接成一棵树形网络，任意两个基站有且仅有一条路径相连。一场雷击会随机选择并击毁一个基站，导致整个网络分裂成若干个互不连通的子网。将每个子网包含的基站数目称为该子网的大小。记随机击毁一个基站后，产生的所有子网里最大的大小值为 $S$。若被击毁的基站是从所有基站中等概率选取，试求 $S$ 的数学期望。

基站总数 $n$ 满足 $1 \le n \le 10^5$。

输入描述

第一行输入一个整数 $n$，表示基站的数量。接下来的 $n-1$ 行，每行输入两个整数 $u$ 和 $v$，代表基站 $u$ 与基站 $v$ 之间有一条光纤直接连接。基站的编号为 $1$ 到 $n$。

保证 $1 \le n \le 10^5$，$1 \le u, v \le n$。