Problem 4E. 最大社交深度和

Problem 4E. 最大社交深度和

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem 4E. 最大社交深度和

时间限制:2s

空间限制:256MB

题目背景

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

题目描述

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

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

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

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

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

image.png

输入格式

  • 第一行有一个整数\(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]\)

2023秋 悬赏令第四周

未参加
状态
已结束
规则
OI
题目
6
开始于
2023-10-29 18:30
结束于
2023-11-05 00:00
持续时间
149.5 小时
主持人
参赛人数
83