自动搬运

查看原文

来自洛谷，原作者为

	Sol1 博客：sol1.netlify.app

搬运于2025-08-24 22:42:50，当前版本为作者最后更新于2022-12-14 15:58:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

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

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

首先交换一下求和顺序。

$$\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)$。

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