Problem 4E. 最大社交深度
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]\)
信息
- ID
- 1002
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 13
- 已通过
- 2
- 通过率
- 15%
- 上传者