[AGC007E] Shik and Travel
题目
给定一棵n节点的 以1为根的 满二叉树 (每个非叶子节点恰好有两个儿子)
n?1 条边. 第ii条边连接 i+1号点 和 ai, 经过代价为vi
设这棵树有m个叶子节点
定义一次合法的旅行为:
(1) 旅行m+1天, 旅行从11号点出发, 最后回到11号点
(2) 第 1 ..m天, 每天 从上一天的结束点出发, 前往一个叶子节点, 然后结束这一天
(记第0天的结束点为1)
第 m+1 天, 从上一天的结束点出发, 前往1号点
(3) 旅行过程中, 每条边恰好经过两次
定义一天的花费为 : 起点到终点的边权和
定义一次旅行的代价为: 第 2 ..m天中, 花费的**最大值**
求一种最优旅行方案, 使得旅行的代价**最小**
输出最小值
2
1≤ai
0≤vi≤131072
题解
观察到$vi<=131072$，我们可以对答案ans进行二分（这种求最大值的最小，最小值的最大一般都是二分啦）
对于每一个节点$i$维护一堆$(a,b)$表示当前子树存在一条起点，终点到$i$距离分别为$a,b$且最长路径不超过$ans$的遍历完整棵子树的方案
现在讲如何合并
因为这是满二叉树，所以当前点i的方案肯定是从左儿子$lc$走到右儿子$rc$，或者反过来.
假设起点在左儿子，那么方案就是$(a,b)=(lc.a+cost_left,rc.b+cost_right)。
但是这个过程中还有$lc.end -> i -> rc.start$这条路径
所以还要满足$lc.b+cost_left+cost_right+rc.a<=ans$
但是，我们不可能对于每个$(lc.a,lc.b)$扫描所有的$(rc.a,rc.b)$
因此，对于相同的a，我们只保留最小的b，b也是同理。
另外对于$(a,b)$，如果能找到$(c,d)$使得$c<=a,d<=b$那么(a,b)就没有保留的必要
所以，我们在回溯时把每个节点的(a,b)对a从小到大排序
因为a递增，所以b递减（否则就没有保留的必要）
所以我们在合并时可以用双指针来加速合并（具体看代码）。
至于合并起点在lc内与起点在rc内的情况，可以用归并排序的思想
时间复杂度为$O(n*logn*logv)$
如果改为用数组来存每个节点的vector的话会快很多
代码
#include#include #include #include #include