← 返回题目列表

Codeforces · 1187/E

E. 树画

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 个顶点组成的树(无向连通无环图)。你正在这棵树上玩游戏。

最初所有顶点都是白色的。在游戏的第一回合,您选择一个顶点并将其涂成黑色。然后,在每一回合中,您选择与任何黑色顶点相邻(通过边连接)的白色顶点并将其涂成黑色。

每次当你选择一个顶点时(即使在第一回合),你获得的点数等于仅由包含所选顶点的白色顶点组成的连通分量的大小。当所有顶点都涂成黑色时游戏结束。

让我们看下面的例子:

顶点 $$$1$$$ 和 $$$4$$$ 已漆成黑色。如果您选择顶点 $$$2$$$,则由顶点 $$$2、3、5$$$ 和 $$$6$$$ 组成的连通分量将获得 $$$4$$$ 点。如果您选择顶点 $$$9$$$,则由顶点 $$$7、8$$$ 和 $$$9$$$ 组成的连通分量将获得 $$$3$$$ 点。

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

输入

第一行包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \le n \le 2 \cdot 10^5$$$)。

接下来的 $$$n - 1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$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

注意

第一个示例树显示在问题陈述中。