这类题感觉相对是比较套路的，但实际写起来坑点比较多，如需要控制好枚举的上下界，以及要考虑新状态是否会被覆盖等问题。 一般来说，大多数树上背包都是 01 背包，因此转移时要注意好内外层循环枚举的方向，以及确保新状态不被覆盖和不会重复考虑，为了避免上面的情况通常可以使用一个 tmp 数组将答案暂存下来，转移完再对 dp 数组进行更新（也可以转移前就存下…

圆的扫描线算法 引入 平面上有 $n$ 个圆，圆之间没有公共点，即圆之间要么包含，要么相离。此时圆要么都是一个包含一个，要么都是同级并列的，不难发现这很像树的结构，那我们不妨将圆的包含关系看做树的边然后建树，这样就会形成一个森林。我们可以给森林一个超级源点，将森林中所有树的根连起来，此时森林就变成了一棵树，相当于此时原点处有一个半径无限大的圆，所有…