题解

思路

对顶点 $u$，记执行 $ exttt{dfs}(u)$产生的序列为$T_u$。它按输入顺序连接若干块：

序列可能因为共享子图而指数增长，不能在完整数据中真正展开。对于任意序列，只需维护其中 $0$ 的数量、$1$ 的数量和逆序对数。

若把序列 $A$ 与 $B$ 连接，则新增的跨区间逆序对数为

做法

子任务 1

图为有向树时，每条边只在 DFS 中经过一次，$|Z|=N-1$。可以按题意显式遍历：遇到 $1$ 就增加已见的 $1$ 数量，遇到 $0$ 就把此前的 $1$ 数量加入答案。

子任务 2

当 $N\le20$ 时，DAG 中的路径数至多为指数规模。直接按题意展开 DFS 调用树，并用同样的方法统计产生的二进制序列。

完整算法

先求图的拓扑序，再按逆拓扑序计算每个 $T_u$ 的三元组 $(z_u,o_u,inv_u)$。

对一条权值为 $w$、终点为 $v$ 的边，它对应的块是 $[w]+T_v$。块内逆序对数为

而块中的 $0$、$1$ 数量分别在 $z_v,o_v$ 基础上加入边权本身。按照出边输入顺序逐块连接，并用连接公式累计跨块逆序对。

正确性证明

对任意顶点 $u$，其 DFS 输出恰由各条出边对应的 $[W_{u,j}]+T_{L_{u,j}}$ 按输入顺序连接而成。逆拓扑处理时，所有子顶点的三元组均已正确得到。

每个块内部的逆序对由子序列内部逆序对和“开头边权为 $1$、后面子序列元素为 $0$”两部分组成。连接当前前缀与新块时，所有新增逆序对恰由前缀中的 $1$ 和新块中的 $0$ 配对，数量为二者数量之积。除此之外没有跨块逆序对。

因此，逐块合并后得到的三元组与真实 $T_u$ 完全一致。由逆拓扑归纳，顶点 $1$ 的逆序对数正确，即为所求答案。

复杂度

设边数为 $M$。完整算法的时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。