#agc007e. [agc007_e]Shik and Travel
[agc007_e]Shik and Travel
问题描述
样例输入 1
样例输出 1
在这个国家中,有 个城市,编号从 到 ,它们之间通过 条双向道路相连。从图论的角度看,连接每对城市的路径都是唯一的。也就是说, 个城市形成了一棵树。此外,如果我们将城市 视为这棵树的根节点,那么这棵树将是一棵满二叉树(当且仅当树中的非叶节点都恰有两个子节点时,树称为满二叉树)。道路的编号从 到 。第 条道路连接城市 和城市 。当你经过第 条道路时,你需要支付的过路费是 (如果 为 ,则表示该道路不需要过路费)。
该公司在城市 给每位员工提供一个家庭旅行,并支付了大部分的过路费。每位员工可以自己设计旅行计划。也就是说,在每天的旅行中,他/她可以决定自己想要参观的城市以及每天晚上在哪个城市住宿。然而,有一些限制。更多细节如下:
- 旅行必须从城市 开始并在城市 结束。如果树形成的叶子节点数为 ,那么旅行的天数必须是 。除了最后一天外,在每天结束时,员工必须在一个叶子城市的某个酒店住宿。在整个旅行过程中,员工必须恰好一次地住在所有叶子城市。
- 在整个旅行过程中,必须恰好经过全国所有道路两次。
- 员工自己需要支付的过路费金额是旅行中一天的最大总过路费(不包括第一天和最后一天)。剩余的过路费将由公司支付。
Shik 是这家公司的一名员工,对于他的旅行,他只希望他自己需要支付的过路费最少。请帮助 Shik 设计满足他期望的旅行计划。
约束条件
- 对于所有 ,
- 对于所有 ,
- 是整数
- 给定的树是满二叉树
输入
输入以以下格式从标准输入给出:
输出
输出一个整数,表示 Shik 自己在旅行过程中需要支付的最少过路费金额。
样例解释 1
树形成的叶子节点有 个(城市 、、 和 ),所以旅行的天数必须是 。有 种可能的叶子城市住宿安排方式,但其中一些是无效的。例如, 和 是有效的顺序,但 是无效的,因为该路线通过连接城市 和城市 的道路 次。下图显示了这些安排方式的旅行路线。
对于所有有效的顺序,第 天的总过路费最大为 ,经过了 条道路。
样例解释 2
下图显示了一种解决方案中待留城市的可能安排方式的旅行路线。请注意,第一天和最后一天的过路费始终由公司支付。