题解：P12683 【MX-J15-T3】叉叉学习与自我和解

· · 题解

给定一颗无向无权图的最短路树，问有多少个图是可能的。

先思考无向无权图的最短路树的生成方法，先 BFS 找到每一个点和源点的距离 dis_{0\dots n-1}，对于每一个 i\in[1, n)，选择一个与之相邻且 dis 小一的点，将其连边。

首先给定的边肯定是存在的，我们考虑增加一些边使得图还是有给定的这个最短路树。

容易发现，增加一些边后仍然合法的冲要条件是 dis 不变。

我们还可以发现：若新加入边集 E_1 后的图是合法的，新加入边集 E_2 后图还是合法的，那么加入 E_1\cup E_2 后图也是合法的。若新加入边集 E_1 后的图是合法的，那么对于任意 E_2\subseteq E_1，加入 E_2 也是合法的。

于是这道题转化为：求有多少条边，使得新加入这一条边后 dis 不变，输出二的这么多次幂，对 10^9+7 取模。

这样这题就做完了，容易发现新加的这一条边肯定在树上要不然连接两个同层的点，要不然连接两个之跨一层的点。

代码是非常好写的，没有任何细节，比 T2 简单多了。