MCOI R5 E

w33z8kqrqk8zzzx33 · 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) 做法。我们不需要扫描线解决统计可达顺序对。本质是想解决快速统计

可以通过前缀和计算。