markdown

E. 树上涂色游戏

时间限制：每个测试点 $2$ 秒
内存限制：每个测试点 $256$ MB
输入：标准输入
输出：标准输出

题目描述

你有一棵由 $n$ 个节点组成的树（即一个无向连通无环图）。你在这棵树上进行一个游戏。

一开始，所有节点都是白色的。在游戏的第一回合，你选择一个节点并将其涂成黑色。在之后的每一回合，你选择一个与某个黑色节点相邻（即通过一条边相连）的白色节点，并将其涂成黑色。

每次你选择一个节点时（包括第一回合），你会获得一定的分数，分数等于当前包含该节点的、仅由白色节点构成的连通块的大小。当所有节点都被涂成黑色时，游戏结束。

请看下面的例子：

节点 $2$ 和 $4$ 已经被涂成黑色。如果你选择节点 $5$，你将获得由节点 $3$、$5$ 和 $6$ 构成的连通块的大小，即 $3$ 分。如果你选择节点 $8$，你将获得由节点 $7$、$8$ 和 $9$ 构成的连通块的大小，即 $3$ 分。

你的任务是最大化你获得的总分数。

输入格式

第一行包含一个整数 $n$ —— 树中节点的数量（$2 \le n \le 2 \cdot 10^5$）。

接下来的 $n-1$ 行每行描述一条树边。每条边由两个整数 $u_i$ 和 $v_i$ 表示，即该边连接的两个节点的编号（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。

输入保证这些边构成一棵树。

输出格式

输出一个整数 —— 在最优策略下你能获得的最大分数。

样例

样例输入 1

9
1 2
2 3
2 5
2 6
1 4
4 9
9 7
9 8

样例输出 1

36

样例输入 2

5
1 2
1 3
2 4
2 5

样例输出 2

14

提示

第一个样例中的树结构如题目描述中所示。