题目描述 小 Q 有一个属于自己的竹园。 这个竹园有 n 个点和 n−1 条双向边,保证任何两个点直接或间接可达。每个点上种了一棵竹子,竹子会在每一天夜里都会长高 1 厘米,初始时竹子的高度都是 1 厘米。 每一天白天,小 Q 可以在花园中巡逻并砍伐竹子。具体来说,他每天可以选定起点 u 和终点 v,沿着唯一的最短路从 u 走到 v,并将路上的所有竹子砍为 1 厘米。 小 Q 不希望竹子长的太高,他想知道,在接下来的 109 天期间,竹子达到的最高高度最小是多少。 输入格式 第一行一个整数 n,表示点的个数。 接下来 n−1 行每行两个整数 u,v,表示存在一条 u 到 v 的双向边。 输出格式 一行一个整数,表示竹子达到最高高度的最小值。 样例 Input 1 3 1 2 2 3 Output 1 2 提示 对于 100% 的数据,2≤n≤106,保证任何两个点可达。 子任务一(20 分):第 i 条边从 i 连向 i+1 子任务二(20 分):n≤10 子任务三(20 分):n≤1000 子任务四(40 分):无附加限制
时间: 2023-06-27 16:03:07 浏览: 73
思路
本题其实是一道二分答案的题目,我们可以二分竹子的最高高度 $h$,然后判断在 $109$ 天内能否将所有竹子都砍成高度小于等于 $h$,如果能够,则答案合法,可以继续往小的二分,否则答案不合法,需要往大的二分。
那么如何判断一个高度是否合法呢?我们可以考虑每一天白天进行的操作,即选定起点 $u$ 和终点 $v$,沿着唯一的最短路从 $u$ 走到 $v$,并将路上的所有竹子砍为 1 厘米。如果对于某个高度 $h$,在 $109$ 天内能够将所有竹子都砍成高度小于等于 $h$,则说明该高度是合法的。
但是直接暴力枚举每个起点和终点并计算最短路是不可行的,因为时间复杂度是 $O(n^3)$ 的,无法通过本题。我们需要优化这一步。
我们考虑从根节点开始遍历整棵树,对于每个节点 $u$,我们维护以下信息:
- $cnt_u$ 表示节点 $u$ 子树中高度大于 $h$ 的竹子数量。
- $mx_u$ 表示节点 $u$ 子树中的竹子最大高度。
- $sum_u$ 表示节点 $u$ 子树中的竹子高度总和。
这三个量都可以通过节点 $u$ 的儿子节点得到。具体来说,对于节点 $u$ 的每个儿子节点 $v$,我们可以得到以下信息:
- $cnt_v$ 表示节点 $v$ 子树中高度大于 $h$ 的竹子数量。
- $mx_v$ 表示节点 $v$ 子树中的竹子最大高度。
- $sum_v$ 表示节点 $v$ 子树中的竹子高度总和。
那么如何通过节点 $u$ 的儿子节点 $v$ 得到节点 $u$ 的信息呢?我们可以考虑递归地计算,对于每个儿子节点 $v$,我们先递归计算出 $v$ 的信息,然后根据 $v$ 的信息更新 $u$ 的信息:
$$ cnt_u += cnt_v $$$$ mx_u = \max(mx_u, mx_v) $$$$ sum_u += sum_v + cnt_v \times (mx_v - h) $$
最后,我们可以通过 $cnt_1$ 判断当前高度是否合法,如果 $cnt_1 \le 109$,则说明高度 $h$ 合法,否则高度不合法。
时间复杂度
对于每个高度 $h$,我们需要遍历整棵树计算一次,时间复杂度为 $O(n)$。再加上二分,总时间复杂度为 $O(n \log w)$,其中 $w$ 表示竹子高度的上限,本题中 $w=109$。
参考代码
以下为 AC 代码:
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)