P13808 [CERC 2022] Deforestation
题目描述
你想要从你的土地上移除一棵大树，但它太大了，你无法一次性搬走。若你一次最多能搬运 $W$ 重量，你需要把这棵树切成多少段才能搬走？
这棵树有一根主干与地面相连，并且可以分出多根分支。所有这些分支还可以继续分叉，依此类推。因此，树的每一段都是一段连续的木头，可能会分出多个分支，也可能没有。
你可以在树的任意位置切割：起点、终点或任何一段的中间。你可以把分叉点看作树上的一个极小的部分，也就是说，你可以在分叉前后立即切割，而不会增加主干的重量，但这会影响子分支是作为一个整体被切下，还是只切下其中一根分支。
输入格式
输入的第一行包含一个整数 $W$，表示你一次能搬运的最大重量。下一行开始描述树的第一段，也就是主干。
一段树的描述是递归定义的。第一行包含两个整数 $M$（该段的重量）和 $N$（该段末端分出的分支数）。接下来是 $N$ 段树的描述，分别描述每一根分支。
输出格式
输出一个整数，表示你需要把树切成多少段才能搬走。
说明/提示
### 说明
下图展示了样例测试用例的一些可能的切割方案。
:::align{center}
:::
### 输入范围
- $1 \leq W, M \leq 10^9$
- $0 \leq N \leq 10^5$
- 所有树段的总重量不超过 $10^9$。
- 树段总数不超过 $10^5$。
由 ChatGPT 4.1 翻译