AGC007E Shik and Travel

题意 ： 一颗 个节点的二叉树，每个节点要么有两个儿子要么没有儿子。边有边权。

第一天，你从 号节点出发，走到一个叶子节点。然后每一天，你可以从当前点走到另一个叶子。

最后一天需要回到 号节点。要求到过所有叶子并且每条边经过恰好两次。

每天的路费是你走过的路径上的边权和，你的公司会为你报销大部分路费，除了你旅行中所用路费最高的，且行走路线是从叶子到叶子的那一天的路费。

求你自己最少要付多少路费？

，时限 。

---

牛逼题。

考虑二分答案，问题变成判定是否存在每一天路费都不超过 的方案。

由于每条边恰好经过两次，每个子树只能进出各一次，必须要走完所有叶子才能离开。

设 为：处理 的子树，第一个叶子到根的距离不超过 ，最后一个叶子到根的距离不超过 ，中间的路径都不超过 的方案是否存在。

显然有 。

记 分别为 的左右儿子， 分别为到左右儿子的距离。

转移：

---

朴素实现复杂度交劣，考虑简化状态，优化转移。

若 ，那么所有 均为 。

于是只需要记录 的“下包络线”。

记 ，即每个 对应的 的最小值。

同时，若 那么 是不必处理的（即考虑为分段函数）。

转移为：

---

设分段函数 的段数分别为 。

每个 都只会对应唯一一个 ，故 。

类似启发式合并的复杂度分析，分段函数总段数是 的。

考虑如何计算 对应的分段函数。显然，指针单调扫描即可。

求两个单调函数的 的过程类似于归并。

这样，就能以 的复杂度完成判定，总复杂度为 。