题解：P10805 [CEOI2024] 加油站

tzl_Dedicatus545 · 2024-11-04 15:08:57 · 题解

以及 ppip 是什么啊？？？？他那个题解我现在还没看懂。误导我这种小朋友有意思吗？

我的做法大概只需要点分治和树状数组，是不是很纯良！！！1

但是我树状数组 n 写小了，调了 1h，怎么回事捏？

Page 3.

首先我们点分治，计算经过分治重心 r 的方案数，经典的，我们不考虑算重（实际上两个到根的链在一个子树内），而是对每个子树做容斥。

我们对 u\to r 和 r \to v 产生的加油分别计算，特别的，r 本身的贡献我们在 r\to v 部分计算。

对每个点，我们记录 f_u 表示：如果在 u 点加过油，下次加油在何处？（只考虑 u\to r）

显然 f 只要在 u\to r 的链上二分就行了，顺理成章的，u \to r 部分可以 \Theta(n\log n) 计算。