首页 > 试题广场 >

Orientation Maximize

[编程题]Orientation Maximize
  • 热度指数：7 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一棵由 n 个节点构成的无根树。你需要为树上的每一条边指定一个方向，使得所有节点的“重力势能“之和最大。
\hspace{15pt}定向后的树可以看作一张有向图，节点 u 的“重力势能”定义为节点 u 的出度的平方 {\rm out}(u)^2。
\hspace{15pt}输出该最大值。

【名词解释】
\hspace{15pt}出度：在有向图中，从某节点出发的边的数量称为该节点的出度。

输入描述:
\hspace{15pt}第一行输入一个整数 n \left(1 \le n \le 2 \times 10^5 \right)。
\hspace{15pt}此后 n-1 行，第 i 行输入两个整数 u_i, v_i \left(1 \le u_i, v_i \le n;\, u_i \neq v_i \right)，表示树上第 i 条边双向节点 u_i 和 v_i。


输出描述:
\hspace{15pt}输出一个整数，表示最大能得到的“重力势能”之和。
示例1

输入

4
1 2
1 3
1 4

输出

9
示例2

输入

5
1 2
2 3
4 3
5 3

输出

10
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 13浏览

热门推荐

相关试题

Orientation Maximize

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号