自动搬运

查看原文

来自洛谷，原作者为

	tzl_Dedicatus545 忙碌着 无为着 继续

搬运于2025-08-24 23:01:27，当前版本为作者最后更新于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)$ 计算。

$r\to v$ 如何计算？首先在加油地点本身计算是毫无道理的（考虑目的地不同可能会导致加油地不同）

我们记 $h_u$ 表示有多少点 $u$ 最终会在 $fa_u$ 处加油，其对答案的贡献就是 $sz_u$。

这样就可以转移了啊！初始的第一次“经过 $r$”的贡献是简单的，接下来就只在 $v\to r$ 链上转移了，我们对此用数据结构维护就行了。

大概是单点加，区间查，但是树状数组不能动态开点/ll，所以你要写线段树。

时间复杂度 $\Theta(n\log^2{n})$。