【11.08测试】铲雪机的一些说明

首先拿到本题第一时间能抽象出的题意相关内容为树上路径覆盖。
然后考虑怎么做，因为树上路径覆盖问题为树上组合优化问题，树上组合优化大概有两种思路树上贪心&树形dp。
对于树上路径覆盖问题，这两种思路就为树上贪心&树上插头dp。
看到数据范围为 \(n \leq 200000\)，如果是 dp 的话，状态数就只能是 \(O(n)\) 的，但本题必须要记录 \(a_u\) 才能 dp。所以我们先考虑树上贪心。
怎么贪心？对于一个点 \(u\) 来说，\(u\) 的儿子结点能尽量往上就往上，不能往上再说，可以证明这种方法一定是正确的。
现在进行分类讨论：

• \(u\) 的儿子 \(v\) 往上的次数 小于 当前的 \(a_u\)，那么 \(a_u\) 减去 \(v\) 往上的次数。
• 否则，就表明现在已经往上的次数已经不够了，设冗余的次数的 \(x\)，则最终答案 \(ans\) 加上 \(x\)。

于是就做完了。