P5129 不可思议的迷宫 题解

老莽莽穿一切 · 2021-10-16 09:18:24 · 题解

更好的阅读体验

这道题难度不大，但是坑点很多，下面我们一一清点 （拉清单） 。

首先，最不坑的坑点，i\to j 和 j\to i 分开计算，i\to i 只算一次。

然后，只要路径上的节点与环有交集，路径就可以从环的两侧走，这一点在样例里有部分体现。

最坑的点，若起点或终点在环上，则可以在从起点出发之前（到达终点之后）绕环一周，同样的，如果起点和终点重合在环上，则可以经过 0 的长度直接到达，也可以绕环一周后到达，你的路径中只要有一个点在环上，路径就可以从环上绕一圈，比如下面这张图中 1\to5 的路径有\color{red}{红色}和\color{blue}{蓝色}标出来的两条 （画图技术有限） ：

知道了这些坑点，其实这道题难度不大，下面开始分析做法。

我们发现如果枚举每个起点和终点，时间就炸了，所以我们可以枚举每条边，考虑每条边被经过的次数。

另外，直接计算期望不方便，不妨先计算路径和，再除以总方案数。

1 非环边

如果一条边是非环边，这条边考虑起来就相对简单，如果起点和终点在它同一侧，则不可能经过它，因为没法回去，如果起点和终点在它异侧，则肯定会经过它，所以直接将左右两边点数乘起来，再乘 2（将起点和终点对调）就是答案了。

2 环边

如果一条边在环上，那么只要一条路径与环有交集，就肯定有 \dfrac{1}{2} 的概率经过这条边，所以问答题转化为有多少条路径会经过环。

我们分情况讨论。

首先，约定总点数为 n ，环上的点数为 c ，不在环上但和环上的点有直接边相连的第 i 个点的子树大小为 v_i 。

2.1 两个端点都在环上

如果两个端点都在环上，则这条路径肯定只能沿着环的某个方向走，一定会经过环，环上的每个点都可以作为起点，也可以作为终点，方案数是 c^2 。

2.2 只有一个端点在环上

这个也很简单，显然，根据上面的坑点，这种情况也肯定会存在路径经过环，如果有一个端点在环上，则一个端点取在环上，方案数是 c ，另一个端点取在环外，方案数是 n-c ，答案就是 2c(n-c) ，乘 2 的原因同上。

2.3 两个端点在两个不同的子树内

这里的不同不仅仅是根节点在环上的编号不同，还有同一个环上节点的不同儿子的子树，这个原因上面坑点已经给出解释，这个其实也比较好算，你其实就是选取一个子树，在其中任取一点作为起点，再选取另一个子树，任选一点作为终点，方案数如下：

这个式子是 n^2 级别的，肯定不行，我们要进行优化，如何优化呢？我们可以通过构造两个线性可求的式子进行相减，有初中水平知识的可以注意到完全平方公式，没错，我们只要用完全平方公式减去平方和就好了，原因如下：

完全平方式展开后就变成了下面。

观察发现只少了一个 [i\neq j] ，我们可以专门把这部分取出来，即 i=j 的情况：

所以方案数就是：

这样我们就分情况讨论完毕了，接下来就是代码实现。

代码实现

先把基环树上的环找到，我这里用的是一种冷门到极点的写法（也许只有我在用），你们可以使用自己的写法，或者查看别的题解，找到环以后就直接统计上面约定的 c 和 v ，再统计，最后别忘了乘 n^2 的逆元。

c++ 代码