You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

简化题意

给定一棵树，现在你要选择一个点集 $V$，使得 $(n - V_1 + 1) > (n - V_2 + 1) > \dots$，而且 $dep_{V_1} \ge dep_{V_2} \ge \dots$，求 $\sum(n - V_i + 1)$ 的最大值。

其中，$dep_i$ 表示第 $i$ 个节点的深度。规定这棵树根节点为 $1$，其深度为 $1$。

小北在圣诞节获得了一颗圣诞树，神奇的是这颗圣诞树上有 $n$ 片叶子和 $n - 1$ 条连接叶子的边，也就是说这真的是一颗“树”。特别的，这棵圣诞树的根为 $1$，根的深度为 $1$。

现在小北共有 $n$ 个彩灯，小北将要把彩灯放在圣诞树上。小北觉得，彩灯越往上放越好看，也就是说节点的深度越浅越好看，因此如果彩灯被挂在第 $i$ 片叶子上，其美丽值为 $n - i + 1$。

小北不会把所有彩灯都挂上。具体地，若小北挂上的彩灯组成的集合为 $\{s_i\}$，则 $s_1$ 应该是集合内的彩灯的最上面一个（深度最小）且是集合内的彩灯的最美丽的一个 ，$s_2$ 是第二靠上的且是第二美丽的，依次类推。注意小北允许有彩灯被挂在同一层上。

问整棵树的彩灯美丽值之和最大是多少。

Input

本题共读入 $n$ 行。

• 第 $1$ 行：$1$ 个整数 $n$，表示树的节点数；
• 第 $2 \sim n$ 行：第 $i + 1$ 行 $2$ 个整数 $u_i, v_i$，表示第 $i$ 条边连接 $u_i$ 和 $v_i$。

Output

• 输出仅 $1$ 行 $1$ 个整数：整棵树的最大的彩灯美丽值之和。

Sample

5
1 2
5 2
2 3
4 1

13

选择 $1, 2, 3, 5$ 这些节点，满足 $b_1 > b_2 > b_3 > b_5$，且 $dep_1 \le dep_2 \le dep_3 \le dep_5$。其中 $b_i$ 表示第 $i$ 个节点的美丽值，$dep_i$ 表示第 $i$ 个节点的深度。其总美丽值为 $b_1 + b_2 + b_3 + b_5 = 5 + 4 + 3 + 1 = 13$。

5
1 2
1 3
2 4
2 5

15

选择所有点即可。

Limitation

• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，保证输入数据可以构成一颗树。