← 返回题目列表

Codeforces · 2117/F

F. 野花

中文机器翻译题面 查看原题

Yousef 有一个有根树$$$^{\text{*}}$$$,由 $$$n$$$ 个顶点组成,根位于顶点 $$$1$$$。您想给 Yousef 一个长度为 $$$n$$$ 的数组 $$$a$$$,其中每个 $$$a_i$$$ $$$(1 \le i \le n)$$$ 可以是 $$$1$$$ 或 $$$2$$$.

设 $$$s_u$$$ 表示 $$$a_v$$$ 的总和,其中顶点 $$$v$$$ 位于顶点 $$$u$$$ 的子树 $$$^{\text{†}}$$$ 中。尤瑟夫思考着这棵树 特别 如果 $$$s$$$ 中的所有值都是 成对不同 (即所有子树总和都是唯一的)。

你的任务是帮助 Yousef 计算不同数组 $$$a$$$ 的数量,这些数组导致树被 特别。如果存在索引 $$$i$$$ 使得 $$$b_i \neq c_i$$$,则两个数组 $$$b$$$ 和 $$$c$$$ 不同。

由于结果可能非常大,您应该打印它对 $$$10^9 + 7$$$ 取模。

$$$^{\text{*}}$$$树是具有 $$$n - 1$$$ 边的连通无向图。

$$$^{\text{†}}$$$顶点 $$$v$$$ 的子树是在到根的简单路径上经过 $$$v$$$ 的所有顶点的集合。请注意,顶点 $$$v$$$ 也包含在集合中。

输入

第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。

每个测试用例由几行组成。测试用例的第一行包含一个整数 $$$n$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — 树中的顶点数。

接下来是 $$$n−1$$$ 行,每行包含两个整数 $$$u$$$ 和 $$$v$$$ $$$(1 \le u,v \le n, u \ne v)$$$ 描述由一条边连接的一对顶点。保证给定的图是一棵树并且没有循环或多重边。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 $$$x$$$ — 导致树为以下形式的不同数组 $$$a$$$ 的数量 特别,模 $$$10^9 + 7$$$。

示例

输入
复制

7
2
1 2
8
1 2
2 3
3 8
2 4
4 5
5 6
6 7
10
1 2
2 3
3 4
4 5
5 6
4 7
7 8
4 9
9 10
7
1 4
4 2
3 2
3 5
2 6
6 7
7
1 2
2 3
3 4
3 5
4 6
6 7
7
5 7
4 6
1 6
1 3
2 6
6 7
5
3 4
1 2
1 3
2 5

输出
复制

4
24
0
16
48
0
4

注意

第五个测试用例中给出的树: