← 返回题目列表

Codeforces · 1777/D

D. 一棵树的分数

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

给你一棵由 $$$n$$$ 节点组成的树,根部为 $$$1$$$。每个节点在 $$$t=0$$$ 时刻的值为 $$$0$$$ 或 $$$1$$$。

在任何整数时间$$$t>0$$$,节点的值成为其子节点在时间$$$t - 1$$$的值的按位异或;叶子的值变成 $$$0$$$ 因为它们没有任何子节点。

令 $$$S(t)$$$ 表示时间 $$$t$$$ 时所有节点的值之和。

令 $$$F(A)$$$ 表示 $$$t$$$ 所有值的 $$$S(t)$$$ 之和,使得 $$$0 \le t \le 10^{100}$$$,其中 $$$A$$$ 是树中 $$$0$$$s 和 $$$1$$$s 的初始分配。

任务是找到树中 $$$0$$$ 和 $$$1$$$ 的所有 $$$2^n$$$ 初始配置的 $$$F(A)$$$ 之和。打印 $$$10^9+7$$$ 模的总和。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树中的节点数。

每个测试用例接下来的 $$$n-1$$$ 行各包含两个整数 — $$$u$$$、$$$v$$$ 表示 $$$u$$$ 和 $$$v$$$ 之间的边缘 ($$$1 \le u, v \le n$$$)。

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

输出

输出每个测试用例的模 $$$10^9+7$$$ 的总和。

示例

输入 #1

1
6
1 2
1 3
3 4
3 5
3 6

输出 #1

288

注意

让我们找到 $$$F(A)$$$ 配置 $$$A = [0,1,0,0,1,1]$$$ ($$$A[i]$$$ 表示节点 $$$i$$$ 的值)。最初($$$t = 0$$$)我们的树如下图所示。在每个节点中,显示两个值:该节点的编号和值。此配置的 $$$S(0)$$$ 为 $$$3$$$。

在 $$$t = 1$$$ 时,配置更改为 $$$[1,0,0,0,0,0]$$$。该树如下所示。 $$$S(1) = 1$$$。

在 $$$t = 2$$$ 时,配置更改为 $$$[0,0,0,0,0,0]$$$。该树如下所示。 $$$S(2) = 0$$$。

对于所有 $$$t>2$$$,图形保持不变,因此对于所有 $$$t > 2$$$,$$$S(t)=0$$$。因此,对于初始配置 $$$A = [0,1,0,0,1,1]$$$,$$$F(A) = 3 + 1 = 4$$$ 的值。

对所有可能的 $$$2^{6}$$$ 配置执行此过程会得到 $$$\textbf{288}$$$ 的答案。