← 返回题目列表

Codeforces · 1218/A

A. 气泡反应器

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

你负责 BubbleReactor。它由 $$$N$$$ BubbleCore 与 $$$N$$$ 电线连接而成。每条电线连接两个不同的 BubbleCore。没有 BubbleCore 与多于一根电线连接。

您的任务是通过启动每个 BubbleCore 来启动 BubbleReactor。为了启动 BubbleCore,它需要从已启动的直接连接的 BubbleCore 接收电力。不过,您可以手动启动一个 BubbleCore,无需电源。保证所有BubbleCore都能启动。

在 BubbleCore 启动过程之前,其潜力被计算为它可以启动的 BubbleCore 数量(直接连接到它的不活动 BubbleCore 的数量或之间任意数量的不活动 BubbleCore 的数量,包括其本身)

启动 BubbleReactor,使所有 BubbleCore 的电势之和最大。

输入

第一行包含一个整数 $$$N (3 \leq N \leq 15.000)$$$,BubbleCore 的数量。

接下来的 N 行包含两个整数 $$$U, V (0 \leq U \neq V < N)$$$ 表示 BubbleCore $$$U$$$ 和 $$$V$$$ 之间存在电线。

输出

单个整数,所有 BubbleCore 潜力的最大总和。

示例

输入 #1

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

输出 #1

51

注意

如果我们首先启动 BubbleCup 8,然后按顺序打开核心 7、2、1、3、0、9、4、5、6,我们将得到电位 10 + 9 + 8 + 7 + 6 + 5 + 1 + 3 + 1 + 1 = 51