题解 P8821【[集训队互测 2022] Paths】

· · 题解

好像做麻烦了，喜提最长解。

是个没啥技术含量的硬核分类讨论题。

首先交换一下求和顺序。

\sum_{i=1}^m\sum_{j=1}^m\sum_{u=1}^n\sum_{v=u}^n[I_i\cup (u,v)=I_j\cup (u,v)]

然后考虑对于任意一对 I_i,I_j，分类讨论它们的位置关系。

1 i=j

任意路径均满足条件。

这一部分贡献为 \dfrac{mn(n+1)}{2}。

2 I_i,I_j 有一个端点相同

下面将公共端点记为 r，并钦定其为树的根；然后将两条路径的另一个点分别记为 v_i,v_j。

2.1 I_i,I_j 互不包含

这种情况可以直接跑个 dfs，然后在 v_i,v_j 的 LCA 处统计。

2.2 I_i 包含 I_j

这种情况可以在 I_i 的非公共端点沿 I_j 方向的第一个点（也就是红色路径与 I_j 的交里面最靠近公共点的点）处统计：（将统计的点记为 u）

  1. 如果 v_j=u，则要求红色路径跨过 u。可以预先对每一个点计算跨过一个点的路径的个数。
  2. 否则，要求红色路径的一端在 u 以 v_j 为根的子树中，另一端在 v_j 以公共点为根的子树中。前者只和 u 有关，后者容易在 dfs 过程中统计。

于是枚举每一个点为公共点，然后把所有伸出去的路径端点的虚树建出来，跑上面的 dfs 就可以了。

这部分时间 O(m\log n)，空间 O(n+m)。

3 没有公共端点，I_i 包含 I_j

新路径必须跨过 I_i，于是可以对每一个 I_i 计算出跨过它的路径个数 w_i。

然后就是对于 j 求包含 I_j 且端点不重合的 I_i 的 w_i 之和。

按照套路，用 dfs 序把路径转成二维平面上的点和矩形，然后二维数点即可。

时间 O(m\log n)，空间 O(n+m)。

4 没有公共端点，I_i,I_j 相交但不包含

4.1 I_i,I_j LCA 不同

下面那条路径的两个端点一定有祖先关系。

搞个 dfs，把路径记在 LCA 上。每次遇到一个路径就分别在每一个端点上加上另一个端点的子树大小；遇到一个两端点有祖先关系的路径时求链上和即可。

使用 dfs 序 + 树状数组做到时间 O(m\log n)，空间 O(n+m)。

4.2 I_i,I_j LCA 相同

枚举 LCA，把对应路径的点集拿出来建虚树。然后在虚树上 dfs，遇到一条路径的一个端点的时候先查询另一个端点的子树和，然后在另一个端点上加上另一个端点的子树大小。

使用 dfs 序 + 树状数组做到时间 O(m\log n)，空间 O(n+m)。

5 I_i,I_j 不交

5.1 一条路径跨过 LCA

对于每一个两个端点一定有祖先关系的路径，把下端点的子树大小加到上端点上，然后对剩下的所有路径的两端点（如果有祖先关系，则只有下端点）求子树和即可。

时空均为 O(n+m)。

5.2 没有路径跨过 LCA

直接 dfs 一遍，在 LCA 处统计贡献即可。

需要注意有一条路径的一个端点在 LCA 时需要特殊处理一下。

时空均为 O(n+m)。

然后把这些全拼起来，这题就做完了。时间 O(n+m\log n)，空间 O(n+m)。

代码有点太壮观了，放这了。