CF1749F Distance to the Path 题解

· · 题解

写在前面

前几天打了 CFeduR137，用一些奇怪的方法做出来了 F，幸运地上了紫。由于知道自己实力不太匹配，害怕掉分，所以 R138 就没有打。当天晚上朋友问我比赛打吗，我拒绝了，没有报名。后来想着帮朋友看一看 D 题，发现十分可做，于是感到有点后悔。不过过了 4 题在 div2 的排名是 200 多，不是特别靠前，所以没当回事。等到离比赛结束还有 10 分钟的时候我打开了 F ，也就是这题。然后我惊讶地发现，这题的套路不是跟 tyy 前几天刚讲过的题差不多吗？怎么全场就只有 26 个人过了？？于是我赛后用了 25min 写了一发，然后就过了。
当晚直接就陷入了无尽的后悔。本来可以直接上橙的！不知道下一次这样的机会是在什么时候了。所以说不要害怕下分，勇敢打比赛吧！

不扯了，说回正题。

前置芝士：

没错，就这些。虽然赛时过的人很少，但是这题做法很简单且很巧妙。保证你看完题解后会理解。

题意：

给你一棵树，点有点权，两种操作：

分析：

直接做貌似不太可做，我们先来看简化版的题目。
【魔怔题面】

简要题意：

一棵树，初始所有点权为 1，两种操作：

这个修改操作有点魔怔，不好直接拿数据结构维护。可能有什么淀粉质（点分治）的做法，但是那样代码又长又难写又难调还不一定对，这里介绍一种更为简单的做法。

对于每个节点 i，记 f_{i,j} 表示以 i 为根的子树的第 j 代儿子要乘多少。初始值全为 1.

这样询问操作就很好做了，由于 d\le 40，暴力向上跳即可。考虑怎么修改。

我们给定这样一棵树，现在假设我们要对所有距编号为 4 的节点距离不超过 2 的值乘 k：

从 4 号点开始，按照下方图示的方法处理（红框内就是每次被处理的节点）：

不难发现通过遵循这样“算两步，跳一步”的方法，经过若干次（不超过 (2d+1) 次）处理，所有与 4 号节点距离不超过 2 的点都被处理到了。
这种方法可以扩展到距离为 d。需要特殊处理当前已经跳到根节点的情况，即不再往上跳，直接更新完所有的节点（这里不好描述，建议读者自己画图理解）。

复杂度为 O(qd),可以通过该题。

解析：

回到本题，题目由单点修改变成了区间修改，暴力重复上面的过程复杂度为 O(qnd)，显然不能通过，怎么办呢？

！我会树链剖分！

正解就是造 21 棵线段树，第 i 棵线段树维护 f_{x,i} 的值。先树剖，每次修改的时候，先修改链上所有的点 i 的 f_{i,d} 的值，然后从 lca 处开始，重复上面的“算两步，跳一步”的做法，就可以了。
我们发现需要维护的是一个支持区间修改，单点查询的数据结构，可以改用差分树状数组。这样时间常数较线段树更小，而空间占用也少了 3/4，显然是更优的。（虽然直接写支持区间修改区间查询的线段树也能过，但是你会像我一样喜提 3744ms 最劣解）

复杂度为 O(q\log^2n+dq\log n)。由于 d 与 \log n 同阶，q 与 n 同阶，所以复杂度为 O(n\log^2 n)。

代码：

不建议点进去的代码链接

代码很丑，因为是直接贺的树剖板子，不具有什么参考价值。而且如果你能理解上面的解析，那代码也没有什么必要了。实在需要的话，你可以去看看其他大佬的代码，都是比我强的。

写在最后：

CSP-S2022 rp++。
要积极参加比赛。