自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:31:08，当前版本为作者最后更新于2021-05-04 16:51:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

观察到，一个节点可以到达的节点为若干子树并。特殊的是，对于所有条件可行对，如果固定首事件，则末事件形成若干额外边末事件的子树之和（强于之并）。可以通过对深度大往小归纳证明。

对每一个节点通过 bitset 处理出来这些子树是什么，时间复杂度 $\mathcal O(nm)$，空间复杂度 $\mathcal O(nm/w)$。考虑任意一个额外边计算它的贡献，也就是对每一个询问它在多少条件可行对里为最后经过的额外边。

考虑离线并扫描线：对询问按照左端点排序，从大到小扫描左端点。考虑 $L+1$ 往 $L$ 移动的时候，需要加 $L$ 对这个子树（额外边末事件）的贡献。我们先处理出来这个子树的所有节点，对这些节点和仅对这些节点建立线段树/树状数组。 这里“仅”的意思是离散化并不考虑任何子树外的节点。

我们仅需要在 $L$ 可以达到额外边首事件时候进行对线段树/树状数组的修改，这个可以直接查询 bitset。还需要注意不要将子树重复统计，这个可以通过按照 dfs 序处理末事件，判断一个节点到达的上一个末事件是否覆盖这个，如果覆盖则跳过。

如果最终发现不跳过，就对子树的线段树/树状数组所有标号大于 $L$ 的元素加1。对于所有 $L$ 等于当前 $L$ 的询问就加上贡献，直接在线段树/树状数组上计算 $[L,R]$ 之和即可。

时间复杂度 $\mathcal O((n+q)m\log n)$，空间复杂度 $\mathcal O(nm/w+q)$。

赛后更新：存在优于 $\mathcal O((n+q)m\log n)$ 的 $\mathcal O((n+q)m)$ 做法。我们不需要扫描线解决统计可达顺序对。本质是想解决快速统计

$$\sum_{l\le i<j\le r}[i\Rightarrow E][E\Rightarrow j] $$

可以通过前缀和计算。