Problem 4E. 最大社交深度和

时间限制：2s

空间限制：256MB

题目背景

在社交网络中，用户可以抽象为一个节点。用户与用户之间的关系可以抽象成一张拓扑结构图。例如粉丝关系拓扑图可以用一张有向图描述，从A到B的边可以表示A关注了B等。

题目描述

在\(tsingpig\) 开发的社交网络中，每个用户节点可以与其他用户建立社交关系，这种关系一定是双向的，所以用无向边表示。

现有一个拥有\(N\)个用户节点、\(N-1\) 项社交关系（即\(N-1\) 条无向边）的无根树形社交网络图。\(tsingpig\) 为这个社交网络定义了评价一个用户的指标—— 社交深度和：以该用户为树根节点的有根树中，所有节点的深度之和。

其中，有根树中节点的 深度定义为节点到树根节点的路径上的点的数量。 显然，树根的深度为1。

现在，希望找到社交网络中的一个用户，他的社交深度和最大，返回该最大值。

例如，在下面图左侧的无根树中，如果选择用户2为树根，转换为右侧树，其所有节点的深度之和为23（未必是最大社交深度和）。

输入格式

• 第一行有一个整数\(N\)，表示社交关系树的节点个数为\(N\)。
• 接下来有\(N-1\)行，每一行两个整数\(u,v\)，表示存在一条社交关系边连接\(u,v\)。

输出格式

输出一行一个整数，最大社交深度和。

样例输入 1

6
3 2
2 4
4 5
4 6
4 1

样例输出 1

18

解释：选择用户3为树根，社交深度和 = 1 + 2 + 3 + 4 + 4 + 4 最大。

样例输入 2

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

样例输出 2

28

解释：选择用户1为树根，社交深度和最大。

数据范围及限制

对于60%的数据，\( N \in [10,5000]\)

对于100%的数据，\( N \in [10,5 \times 10^5]\)