自动搬运

查看原文

来自洛谷，原作者为

	EricWan 一只菜鸡。

搬运于2025-08-24 23:17:24，当前版本为作者最后更新于2025-06-02 11:14:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

先思考无向无权图的最短路树的生成方法，先 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 简单多了。