树上染色（painting）

题目描述

给定一棵有 $n$ 个节点的树。树是一张无向、连通、无环图。

一开始，所有节点都是白色。

你要在这棵树上进行染色游戏：

1. 第一次操作时，你可以任选一个白色节点，将它染成黑色；
2. 之后每一次操作，你必须选择一个白色节点，并且这个节点要与至少一个黑色节点相邻，然后将它染成黑色。

每次选择一个节点染黑时，包括第一次操作，你会获得一定分数。

得分规则如下：

当前选择的节点仍然是白色时，观察只由白色节点组成的连通块。你本次获得的分数，等于包含该节点的白色连通块大小。

当所有节点都被染成黑色后，游戏结束。

请你求出，在最优操作顺序下，能够获得的最大总分。

输入格式

第一行包含一个整数 $n$，表示树的节点数量。

接下来 $n-1$ 行，每行包含两个整数 $u_i,v_i$，表示树上的一条边。

保证给出的边构成一棵树。

输出格式

输出一行一个整数，表示按照最优策略进行染色时，可以获得的最大总分。

输入输出样例 #1

输入 #1

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

输出 #1

36

样例解释 #1

这棵树共有 $9$ 个节点。可以证明存在一种最优策略可以使总得分达到 $36$。

输入输出样例 #2

输入 #2

5
1 2
1 3
2 4
2 5

输出 #2

14

样例解释 #2

这棵树共有 $5$ 个节点。

如果第一次选择合适的节点作为染色起点，之后不断向相邻白色节点扩展，可以获得最大总分 $14$。

数据范围与约定

对于所有测试数据，保证：

保证输入的 $n-1$ 条边构成一棵树。

特殊性质 $\text{A}$：保证这棵树是一条链。

特殊性质 $\text{B}$：保证这棵树是一棵以 $1$ 为中心的菊花图，即所有其他节点都直接与节点 $1$ 相连。