CF1252B Cleaning Robots

新建的 ICPC 小镇有 $N$ 个路口（编号为 $1$ 到 $N$），通过 $N-1$ 条道路相连。可以从任意一个路口出发，通过一条或多条道路到达其他任意路口。为了确保所有路口都能得到良好维护，政府环境局计划部署最新的高级清洁机器人。除了清洁功能外，每台机器人还具备移动能力，可以沿道路从一个路口移动到与之相连的其他路口。然而，正如你所猜测的，这些机器人价格不菲。因此，环境局正在考虑如下部署方案。 设 $T_k$ 为第 $k$ 台机器人需要清洁的路口集合（即机器人的任务），且 $|T_k| \ge 1$ 表示 $T_k$ 中路口的数量。$T_k$ 中的路口必须构成一条路径，即存在一个序列 $v_1, v_2, \dots, v_{|T_k|}$，其中 $v_i \in T_k$ 且 $v_i \neq v_j$（对于所有 $i \neq j$），并且序列中相邻的路口通过道路直接相连。所有机器人的 $T$ 的并集等于 ICPC 小镇的所有路口集合。同时，任意两台机器人不能有共同的路口，即 $T_i \cap T_j = \emptyset$（当 $i \neq j$）。 为了避免市民对低效运作的投诉，部署方案应当是不可约的；换句话说，不存在两台机器人 $i$ 和 $j$，使得 $T_i \cup T_j$ 仍然构成一条（更长的）路径。注意，环境局并不关心机器人数量是否最少，只要所有任务都是不可约的即可。 你的任务是，给定小镇的布局，统计满足上述所有要求的可行部署方案的数量。一个方案当且仅当满足所有上述条件时才是可行的。 例如，设 $N=6$，道路为 $\{(1,3),(2,3),(3,4),(4,5),(4,6)\}$。共有 $5$ 种可行的部署方案，如下图所示。  - 第一种方案使用 $2$ 台机器人（图中标记为 A 和 B），分别清洁 $\{1,2,3\}$ 和 $\{4,5,6\}$。 - 第二种方案使用 $3$ 台机器人（图中标记为 A、B 和 C），分别清洁 $\{1,3,4,6\}$、$\{2\}$ 和 $\{5\}$。 - 第三种方案使用 $3$ 台机器人，分别清洁 $\{1,3,4,5\}$、$\{2\}$ 和 $\{6\}$。 - 第四种方案使用 $3$ 台机器人，分别清洁 $\{1\}$、$\{2,3,4,6\}$ 和 $\{5\}$。 - 第五种方案使用 $3$ 台机器人，分别清洁 $\{1\}$、$\{2,3,4,5\}$ 和 $\{6\}$。 在本例中，没有其他可行方案。例如，方案 $\{\{1,3\},\{2\},\{4,5,6\}\}$ 不可行，因为任务 $\{1,3\}$ 和 $\{2\}$ 可以合并为更长的路径 $\{1,3,2\}$。方案 $\{\{1,2,3,4\},\{5\},\{6\}\}$ 也不可行，因为 $\{1,2,3,4\}$ 并不是一条路径。

输入的第一行包含一个整数 $N$（$1 \le N \le 100\,000$），表示路口的数量。接下来的 $N-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i < v_i \le N$），表示一条连接路口 $u_i$ 和 $v_i$ 的道路。保证任意两个路口之间都可以通过道路连通。

输出一行一个整数，表示可行部署方案的数量。由于答案可能很大，请对 $1\,000\,000\,007$ 取模后输出。

样例输入输出 #1 的说明 这就是题目描述中的例子。 由 ChatGPT 4.1 翻译