P3345
「题解注释」P3345 [ZJOI2015] 幻想乡战略游戏
[题解 P3345 【[ZJOI2015]幻想乡战略游戏】 - Baka's Blog - 洛谷博客 (luogu.org)](https://kai586123.blog.luogu.org/solution-p3345) 耗时:半个下午 代码注释: ```cpp #include typedef ......
题解 P3345
点分树。 本题的核心问题在于不好直接确定补给站的位置。 但是仔细思考后我们发现,对于当前节点,如果存在一个儿子的答案比它优,那么补给站一定在那个儿子的子树中。 增量为 $w\times(sum_u-2\cdot sum_v)$。当 $v$ 优于 $u$ 时,$2\cdot sum_v>sum_u$。 ......